Order-statistic tree (Augmenting Data Structures)

Need help to show how to use an order-statistic tree to count the number of inversions in an array of size n in time O(n lg n). Note that we call a pair (i,j) an inversion if i < j, but key[i] > key[j]. Thus, an increasing sequence has no inversions. A decreasing list has the maximum number of inversions, n(n-1)/2. I beli ...continues

Select (Medians and Order statistics)

Please review problem and verify the solution. problem --------- In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used. solution --------- Use groups o ...continues

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.