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 believe we start by letting k be the number of inversions in the sequence. We then create an order-statistic tree and store with each node the original index in the sequence. Is there anything else we store in the node and what would be the algorithm for the number of inversions?

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 of k for the analysis. The worst case SELECT will be called recursively on at most n - (n/4 - k) = 3n/4 + k elements. The recurrence is T(n) <= T(ceiling(n/k)) + T(3n/4 + k) + O(n) Solve the recurrence by substitution I believe the solution is the following: T(n) <= T(ceiling(n/k)) + T(3n/4 + k) + O(n) <= c(n/k + 1) + 3cn/k + c(k+1) + O(n) <= c... click for more

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 left subtree and resembles a linked list on right subtree . Predecessor - ? Insert - insert a key that is greater than the max value of the tree Delete - remove an key that is the max value of the tree

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 in radix 2^p. Show that if a string x can be derived from string y by permuting its characters, then x and y hash to the same value. Give an example of an application in which this property would be undesirable in a hash function. solution --------- All permutations can be generated by a sequence of two character interchanges. If two arbitrary characters... click for more

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?