Due: Wed Sept 27 midnight

To understand Range Minima Query data structures, algorithms, and analysis; to design a streaming algorithm.

Task

1. (5 marks) Suppose you have an array A[0..99] that consists of these values:
   [ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 ....0 1 2 3 4 5 6 7 8 9 ]
   Give rows 0 to 9 of the SparseTable for this data. The table should be filled with indices, not values.
2. (5 marks) Construct the Cartesian Tree for the array
   A = [19 4 16 70 55 23 93 11 19 40 32 91 67 88 14 12]
3. (10 marks) Give pseudocode for an algorithm that produces a Cartesian Tree:
   Input:An array A[0..n-1] of integers
   Output:a pointer to the root of a Cartesian tree for A.
   
4. 1. (10 marks) Give a way to construct a bit sequence that is a bijection to the Cartesian Trees of size s (isomorphic under shape, and therefore to range minimum queries). You can and should review the Wikipedia page on Range Minimum Queries. How big is the bit sequence?
   2. (4 marks) Does every bit sequence of that size map to a Cartesian Tree -- and if not, explain exactly which bit strings map to Cartesian Trees of size s. Prove that the number of such bitstrings is equal to the s^th Catalan number.
   3. (6 marks) Given a bit sequence, sketch out an algorithm to construct the Cartesian tree associated with that bit sequence.
5. (4 marks) Consider the RMQ strategy that reduces the problem to RMQ±1. We said in class that the size of the Look-up Table for the boundary blocks is √n lg²n. But the MIT notes say the size of the table is √n lg²n lg lg n. The MIT notes are more accurate: what are they taking into account that our analysis in class did not?
6. (4 marks) Prove (using the Rules of Big-O or the definition of Big-O) that √n lg²n lg lg n is o(n).
7. (5 marks) Write pseudocode for MinContiguousSum that uses constant space (let us assume our integers each fit into a word). Argue briefly why it gives the correct answer.

Next Assignment