Algorithm Engineering 19 January 2019
Name: Surname: Matricola:
Exercise [rank 5+5+5]
Prove that the average height of a Treap built on n keys with random priorities is O(log n).
Prove that in an undirected cuckoo graph of r nodes and n edges, the
probability that two nodes are connected by a path of length L is at most c^{- L}/r, where r ≥ 2cn
Show the streaming algorithm to sample uniformly at random m items out of a sequence of n, and prove its correctness
Exercise [rank 5+3] Let us given the symbols and their probabilities: p(a) = p(b) = 0.05, p(c) = p(g) = 0.1, p(d) = p(f) = 0.2, p(e) = 0.3.
a. Compute the Canonical Huffman code for this distribution
b. Decode the first 3 symbols of the coded sequence 10001011011100…
Exercise [rank 5] Given the undirected and weighted graph
G={(A,B, 2), (A,F, 1), (A,E, 6), (B,C, 6), (B,F, 3), (C,D, 3), (C,F, 5)}. Compute its MST via the Kruskal’s algorithm.
Exercise [rank 5] Given the string S=baobab, compute the Suffix Array, and then derive the LCP array by using the linear-time algorithm seen in class, showing the amount of characters really compared when determining the various LCPs.
