Algorithm Engineering
29 June 2015
Exercise [rank 5] Discuss the optimality of the disk striping technique in combination with multi-way mergesort when sorting N items over D disks, in a model with
internal memory of size M and block size B.
Exercise [rank 4+4] Let us given symbols and probabilities: p(a) = 0.25, p(b)=0.25, p(c) = 0.50.
Decompress the first 4 symbols of the Arithmetic coded bit sequence:
1010110.
Indicate the number of bits emitted by Arithmetic coding as a function of the size of the last interval, motivate its choice and prove its correctness.
Exercise [rank 4+4] Consider the Treap data structure:
Prove that its average height is O(log n), when storing n keys.
Given a set of pairs <key,priority> equal to {(1,7), (2,2), (3,9), (4,4), (5,3), (6,6), (7,0), (8,1)} insert them into a Treap in that order and then execute a Split operation over the key 5.
Exercise [rank 5+4] Given the graph G formed by the weighted edges E={(a,b,3), (a,d,1), (b,d,4), (b,c,5), (b,e,2), (c,d,1), (c,e,4), (d,e,6)}
apply the fully external-memory algorithm to compute the MST by never turning into the semi-external version and without applying the initial permuting step on its nodes.
Compare the solution derived in the previous item with the one obtained by running the Prim’s algorithm, starting from node ‘a’.
