• Non ci sono risultati.

Algorithm Engineering 18 December 2017 First and Last Name: Matricola: Exercise [rank 6]

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Algorithm Engineering 18 December 2017 First and Last Name: Matricola: Exercise [rank 6]"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

Algorithm Engineering 18 December 2017

First and Last Name: Matricola:

Exercise [rank 6]

Given the set of strings S = {abaa, abca, abma, baa, bbb}, build a Patricia trie and show the steps for the lexicographic search of the strings P1 = aaa, P2 = abb.

Exercise [rank 6+3]

Given the sequence of integers (11, 14, 16, 19, 20, 21, 22), show how to encode them based on

- Elias-Fano Code

- Interpolative Code (just one level of recursion, hence 3 numbers)

Exercise [rank 6]

Given the string S = abababc show the result of the full bzip pipeline.

Exercise [rank 6] Given the string T = aba, and the probabilities P(a) = ¾ and P(b) = ¼, show the result of the Arithmetic Coding applied on T. (hint:

Please work with the dyadic fractions, not change them into reals.)

Exercise [rank 3] Given the tree (1,2), (2,x), (2,y), (2,z), (1,3), (3,u), (3,v), of internal nodes {1,2,3} and leaves {x, y, z, u, v}, apply the transformation Euler Tour  Sparse Table and Prefix/Suffix Arrays to answer in constant time lowest common ancestor queries between pair of leaves.

Riferimenti

Scarica adesso ( DOC - 1 pagine - 55.50 KB )

Documenti correlati

Algorithm Engineering 18

[r]

Algorithm Engineering 16 July 2018 Exercise [rank 4+3]

Write the pseudo-code of the Reservoir Sampling algorithm that random samples m items from a sequence of unknown length. Prove that the probability of extracting any element when

Algorithm Engineering 5 September 2017 First and Last Name: Matricola:

 discuss the efficiency of PRIM’s algorithm when the graph grows in

Algorithm Engineering 29 June 2015 Exercise [rank 5]

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

Algorithm Engineering 20 July 2015 Exercise [rank 4+2]

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

Algorithm Engineering 10 September 2015 Exercise [rank 3+3]

Exercise [rank 2+2] Provide the motivation of introducing Universal Hashing, with respect to classic hash functions (such as mod, division,…) and an example of family of

Algorithm Engineering 09 February 2015 Exercise [rank 4+4]

Exercise [points 4+4] Given the array A = [5, 2, 4, 8, 3, 1, 9, 6], build the RMQ data structure but ONLY for RMQ-queries which are either aligned to blocks or overlap

Algorithm Engineering 4 June 2013 Exercise [rank 6]

Prove that the expected reconstruction time of cuckoo hashing is O(n), if it is built over n items and we consider a sequence of a*n insertions, where a is