Weekly Note 5, DM42, fall 2006

Discussion Section October 2

1. Show that a ½-weight-balanced Scapegoat tree has minimal height.
2. Use illustrations to go through the recursive method for the restructuring of a subtree of a Scapegoat tree which is used in Section 6.1, and make it clear which references must be maintained during the process.
3. In Scapegoat trees we often need to know the sizes of subtrees. Instead of computing these, we could consider storing these values in the nodes. Consider the pros & cons of this.
4. One could also register the potential of a node with that node. What could that be used for?
5. Make a sketch of how the insertion procedure should be coded. Note that there are no parents pointers. Assume that you have the following procedures available: restructure(T) restructures the subtree T and count(T) counts the nodes in the subtree T.

Lecture October 4

• Universal hashing, [CLRS01] section 11.3.3.
• Perfect hashing, [CLRS01] section 11.5.

Announcements

• Friday, January 5, 2007 has been set by the administration as the tentative date for the DM42 exam (confirmation pending).