Algorithm Engineering 15 January 2018

Prove that, for any pair of positions i and j in the cuckoo table, the probability that the shortest path connecting ij has length L is c^{-L}/r, where r is the number of

 Recompute the average length of the sorted runs if the Snow Plow is executed over a sequence in which the probability of an item to go in the heap is 2/3 instead of 1/2.  Show

Build a Patricia trie on the set of strings S={aba, abcaba, abcad, bd} and show how it is executed a lexicographic search for the string P1 = acdac,

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

Finally simulate its working over the sequence 3,10,1,6,2,5,3, by showing the sorted blocks it forms with a memory capable to store M=2 integers.. Exercise

 Show the pseudo-code of the variant of binary quicksort that reduces the extra- space used during recursive calls, and comments on its complexity

Assuming that S is on disk and the Patricia trie is in internal memory, with leaf pointers to strings of S, show the I/O-complexity of prefix- searching for a pattern P[1,p]c. [rank

Exercise [rank 6] Prove that the Arithmetic coding algorithm is close to the empirical entropy of a text having length n symbols. Exercise [rank 5] Let us given symbols