• Non ci sono risultati.

Algorithm Engineering 4 April 2019 Exercise [rank 4+4+4]

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Algorithm Engineering 4 April 2019 Exercise [rank 4+4+4]"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

Algorithm Engineering

4 April 2019 Exercise [rank 4+4+4]

1. Show the optimal time complexity of LSD-radix sort, and prove the correctness of the algorithm.

2. Prove that the space complexity of a Perfect Hash Table is O(n).

3. Describe the Snow Plow technique, show and prove the bound on the average length of the sorted runs it forms.

Exercise [rank 5]

Simulate the behavior of the algorithm MultiKey-Quicksort on the following array of 6 strings S=[zoo, horse, bath, abacus, bar, aargh].

Exercise [rank 5]

Given the text T = baab, compress it via Arithmetic coding, using as probabilities of the symbols their frequency of occurrence in T.

Exercise [rank 4+4]

Construct a Treap for the set of pairs <key, priority>: {<3,5>, <9,3>, <15,9>,

<8,1>, <2,4>, <4,8>, <1,11>, <7,7>} using a MIN-heap over the priority.

 Show the execution of a split at the key 6.

Riferimenti

Scarica adesso ( DOC - 1 pagine - 41.50 KB )

Documenti correlati

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 8 April 2015

Use multi-key quicksort to sort the set of strings S = (apex, zob, bus, bat, zig, bue), by assuming that the pivot-string is chosen as the first one of the string-sequence to

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

Algorithm Engineering 25 June 2013 Exercise [rank 4+2]

Discuss the solution, assuming that the distinct items are m &lt; M, but their total length mL &gt; M (so you cannot explicitly store them in memory), and comment on its

Algorithm Engineering 16 July 2013 Exercise [rank 2+2+3]

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