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.

Hint: create a red–black BST where the keys are integers and the values are the items such that the ith largest integer key in the red–black BST corresponds to the ith item in the queue.

Quiz 8-- Princeton Algorithm

Java autoboxing and equals(). Consider two 𝚍𝚘𝚞𝚋𝚕𝚎 values 𝚊 and 𝚋 and their corresponding <tt>Double</tt> values 𝚡 and 𝚢.

• Find values such that (𝚊==𝚋) is 𝚝𝚛𝚞𝚎 but 𝚡.𝚎𝚚𝚞𝚊𝚕𝚜(𝚢) is 𝚏𝚊𝚕𝚜𝚎.
• Find values such that (𝚊==𝚋) is 𝚏𝚊𝚕𝚜𝚎 but 𝚡.𝚎𝚚𝚞𝚊𝚕𝚜(𝚢) is 𝚝𝚛𝚞𝚎.

Hint: IEEE floating point arithmetic has some peculiar rules for 𝟶.𝟶, −𝟶.𝟶, and 𝙽𝚊𝙽. Java requires that 𝚎𝚚𝚞𝚊𝚕𝚜() implements an equivalence relation.

0.0 == -0.0        Double.valueOf(0.0).equals(Double.valueOf(-0.0))

Double.NaN == Double.NaN   Double.valueOf(Double.NaN).equals(Double.valueOf(Double.NaN))

Check if a binary tree is a BST. Given a binary tree where each 𝙽𝚘𝚍𝚎 contains a key, determine whether it is a binary search tree. Use extra space proportional to the height of the tree.

Hint: design a recursive function 𝚒𝚜𝙱𝚂𝚃(𝙽𝚘𝚍𝚎𝚡,𝙺𝚎𝚢𝚖𝚒𝚗,𝙺𝚎𝚢𝚖𝚊𝚡) that determines whether 𝚡 is the root of a binary search tree with all keys between 𝚖𝚒𝚗 and 𝚖𝚊𝚡.

  if (Nodex == null) return true;

  if ( Nodex.value < Keymin || Nodex.value > KeyMax) return false;

  return isBST(Nodex.left, Keymin, Nodex.value) && isBST(Nodex.right, Nodex.value , Keymax)

Inorder traversal with constant extra space. Design an algorithm to perform an inorder traversal of a binary search tree using only a constant amount of extra space.

Hint: you may modify the BST during the traversal provided you restore it upon completion.

Web tracking. Suppose that you are tracking n web sites and m users and you want to support the following API:

• User visits a website.
• How many times has a given user visited a given site?

What data structure or data structures would you use?

Hint: maintain a symbol table of symbol tables.