Sean: Quiz 9-- Princeton Algorithm

Sean: Quiz 9-- Princeton Algorithm

Red–black BST with no extra memory. Describe how to save the memory for storing the color information when implementing a red–black BST.

Hint: modify the structure of the BST to encode the color information.



Document search. Design an algorithm that takes a sequence of n document words and a sequence of m query words and find the shortest interval in which the m query words appear in the document in the order given. The length of an interval is the number of words in that interval.

Hint: for each word, maintain a sorted list of the indices in the document in which that word appears. Scan through the sorted lists of the query words in a judicious manner.

Generalized queue. Design a generalized queue data type that supports all of the following operations in logarithmic time (or better) in the worst case.

• Create an empty data structure.
• Append an item to the end of the queue.
• Remove an item from the front of the queue.
• Return the ith item in the queue.
• Remove the ith item from the queue.

Read full article from Sean: Quiz 9-- Princeton Algorithm