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.