Binary Tree Tree worst case scenario

We know that binary trees are O(n) for these dictionary operations... What is the worst case input scenario for each operation (i.e. a list of numbers in reverse order...) Binary Tree ------------- Mininum - ? Maximum - ? Search - the tree is unbalanced (resembles a linked list) Successor - the tree has one node on le ...continues

Division method for a hash function

Please review the problem and explain each step of the solution listed below, and give me an example of an application which this property would be undesirable in a hash function. problem ---------- Consider a version of the division method in which h(k) = k mod m, where m = (2^p) -1 and k is a character string interpreted ...continues

Edges and graphs

The number of strongly connected components in a graph G is k. By how much can this number change if we add a new edge?

Kruskal's algorithm - graphs

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

Graphs - airport problem

(See attached file for full problem description)

Oral History Data Organization

You are helping scientists analyze oral history data they have collected by interviewing members of a village. From these interviews they have learned about a set of n people (all are dead now) whom we will denote P1, P2, ... Pn. The have also collected facts about when these people lived relative to one another. Each fact ha ...continues

Minimum amount of Base Stations

Let's consider a long, quiet country road with houses scattered very sparsely along it. (Picture the road as a long line segment with an eastern endpoint and a western endpoint.) Further lets suppose that despite the country setting, the residents of all these houses are avid cell phone users. You want to place cell phone bas ...continues

Pseudocode to check if sum of 2 items in an array is 100

Write and explain the pseudocode to check whether there are 2 items in an array of n integers so that their total is 100.

Minimum spanning tree

(See attached file for full problem description)

Topological Sorting

An algorithm for computing a topological ordering of a DAG (Directed Acyclic Graph) repeatedly finds a node with no incoming edges and deletes it. This will eventually produce a topological ordering, provided that the input graph really is a DAG. But suppose that we're given an arbitrary graph that may or may not be a DAG. Ex ...continues