Mini #3, 15451 Fall 2010
========================
This mini is due via *email* to your TA, by 11:59pm Tuesday, Sep 28.
Please use the *exact* subject line "15-451 MINI #3" in your email.
As always make sure to include your name and Andrew ID.
Also, we prefer that you copy your answers directly into the email body, instead
of including attachments. Thanks!
1. Universal Hashing
Consider the following two hash functions h1 and h2 from {1,2,3} to {0,1}:
1 2 3
---+----------
h1 | 1 0 1
h2 | 0 1 0
(i.e., h1(1)=1, h1(2)=0, h1(3)=1, h2(1)=0, h2(2)=1, h2(3)=0)
a) Is the set H = {h1, h2} a universal hash family? Why or why not?
b) What if we modify h1 so that h1(1)=0. Is H = {h1, h2} a
universal hash family now? Why or why not?
2. Treaps/B-Trees
a) True or False: Both Treaps and B-Trees are always balanced
b) Perform an LSF radix sort on the list [451, 251, 211, 410, 412, 212]
(you must show every step of the algorithm and a brief explanation)
3. Tries
Create a trie that stores the following four-letter strings alphabetically.
(Use "$" as an end character. You can draw the tree in the text file.)
{rink, role, rind, ring, rick, roll}