Algorithm Engineering 16 July 2019

Write the pseudo-code of the Reservoir Sampling algorithm that random samples m items from a sequence of unknown length. 2) design an algorithm that determines efficiently, via

Exercise [rank 4+4] Let us given two arrays: A[1,n] of items and [1,n] that denotes the permutation of the positions in the range [1,n], such that [i] is the position where the

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

Compute the Shortest Path Tree from node a using Dijkstra’s algorithm (showing all steps and used data structures)b. Show how to compute the MST of G in the case of an internal memory

[rank 5] Given the string S=aaccacaacc, show the execution of the Skew algorithm for the first level of recursion, thus solving directly the construction of SA^{2,0}, as done

[rank 4] Given the string T[1,9]=ddddaabbcc, compute the Canonical Huffman code for the letters of T assuming as probabilities their empirical frequencies in T.. [rank 5] Given

Define the (s,c)-dense code, where assuming s+c=256, specify how many bytes it occupies to represent integer x as a function of s and c, and comment when it can be better

The parameter vector of the model is composed of the probabilities of each one of four events corresponding to respectively: speciation of the parasite together with a speciation of