Algorithm Engineering 12 June 2017
Exercise [rank 6] Given the text T = ASSISI, illustrate the results of each algorithmic step of the pipeline BWT + MTF + RLE1 + Huffman.
Exercise [rank 6] Given the un-directed graph G consisting of 4 vertices and 5 edges {(1,2, 7), (1,4, 1), (1,3, 4), (2,4, 3), (3,4, 2)}, in which the third component indicates the edge weight, show the execution of the Sybein’s algorithm to build the MST fully in external memory.
Exercise [rank 6] Show the encoding of the first 10 positive integers according to the (s,c)-code with s=1 and c=3, hence s+c = 4 = 22 (comment your calculations).
Exercise [rank 5] Let H be a class of Universal Hash functions h: U -> {0,1,2,...,m-1}
and let S be a subset of U formed by n keys. Prove that, if h is drawn randomly from H, then the tables of the second level of a Perfect Hash occupy O(n) average space.
Exercise [rank 3 + 2 + 2] Consider two sets of pairs <key,priority> equal to S1 = {(1,5), (3,2), (4,6)} and S2 = {(3,7), (10,10)}
insert them into two Treaps (organized as min heaps in their priorities) in the order specified above: so S1 creates Treap T1 and S2 creates Treap T2.
Then motivate why it is possible to execute a Merge operation between T1 and T2.
Finally show the execution of a Merge between T1 and T2 (describe the algorithm and show the final result).
Exercise [lode] Describe when the “strange case” of LZW occurs and how it is solved by the decompression algorithm, by providing also a running example.
