Algorithm Engineering
29 January 2014
1. [rank 3] Let us given symbols and probabilities: p(f) = p(e) = 0.07, p(c)=p(d) = 0.15, p(b)=0.2, p(a)=0.36. Construct the Canonical Huffman code, showing how it is obtained step-by-step.
2. [rank 3] Describe the disk striping technique and comment on its (sub)optimality.
3. [rank 3+3] Given the set of strings S={zoo, baa, bac, aba, dab, dbb, bcc, aaa, dab} sort them by multi-key quicksort and by LSD radix sort.
4. [rank 2+3+3] Build a Patricia trie on the set of strings S={aca, acdaba, acdac, bc} and show how it is executed a lexicographic search for the string P1 = aadab, and P2=acb
5. [rank 2+2+3+3]
a. Given a set S of n items in U, define what is a perfect hash function h: U {0,1, …, m-1}.
b. Given a set S of n items in U, define what is a minimal perfect hash function h: U {0,1, …, m-1}.
c. Given a set S of n items in U, define what is a minimal ordered perfect hash function h: U {0,1, …, m-1}.
d. Assume you are given 6 strings (aa, ab, bb, bc, ca, db) and you wish to construct a minimal ordered perfect hash function. Assume that
rank(x)=1,2,3,4 for the characters x=a,b,c,d respectively. Given a string x’x’’ of two characters, we let the two random functions required by the design of MOPHF as h1(x’ x’’) = rank(x’) * rank(x’’) mod 13 and h2(x’
x’’) = rank(x’) + rank(x’’) mod 13 (so m=13). Design a proper g(t) to construct the final h(t), if this is possible given h1 and h2 above.
