• Non ci sono risultati.

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

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

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

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

Algorithm Engineering

16 July 2018 Exercise [rank 4+3]

1. Write the pseudo-code of the Reservoir Sampling algorithm that random samples m items from a sequence of unknown length.

2. Prove that the probability of extracting any element when the sequence has length n is m/n.

Exercise [rank 5]

Decode the Bzip-encoding 131331 assuming an alphabet {a,b,d} and a position of 5 for the special symbol # in the BWT, counting from 1. (hint: Recall the compression sequence BWT + MTF with list (a,b,d) and counting from 1, and applying RLE only on runs of 1 whose length is encoded in binary)

Exercise [rank 4+3+3]

 Construct a Treap for the set of pairs (<3,5>, <9,3>, <15,9>, <5,1>, <10,4>,

<4,8>, <2,11>, <7,7>) using a MIN-heap over the y-coordinate (i.e. the priority). (The x-coordinate is the key.)

 Show what happens to the treap when the pair <1,2> is inserted.

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

Exercise [rank 4+4]

Let us given a computational model with D disks, memory M, and page size B:

 Show the I/O-complexity of multi-way mergesort (for D=1) and discuss what is worse in terms of I/O-complexity between either reducing the memory from M to sqrt(M) or reducing the block size from B to sqrt(B).

 Describe the technique of Disk Striping and show the I/O-complexity of the multi-way mergesort when applies it on D disks.

Riferimenti

Scarica adesso ( DOC - 1 pagine - 42.00 KB )

Documenti correlati

Algorithm Engineering 19 July 2016

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

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

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