• Non ci sono risultati.

Algorithm Engineering 11

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Algorithm Engineering 11"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

Algorithm Engineering

11 January 2016 Exercise [rank 3+5]

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

correctness.

 State and prove the theorem that establishes the partitioning performance of the multi-pivot selection strategy.

Exercise [rank 3+3] Given the LSD-Radix sort algorithm:

Specify its time complexity as a function of the key length b (in bits) and the number of keys n.

Simulate its working over the sequence of 4 strings (1010,0011,0111,0000) by assuming to group digits 2-bits at a time.

Exercise [rank 4+3] Let us given the integer array A=[3,8,2,1,9,5,11,15]

 Show how to turn the RangeMinimumQuery (RMQ) problem over the generic integer array A into a RMQ problem over an array B formed by entries +1/-1.

 Build a data structure that solves the RMQ problem over B[1,n] using space O(n log n) and O(1) query time.

 Show how to solve RMQ_A(5,7) over the data structure built on B.

Exercise [points 2+3+4] Given a sequence of integers S=(1, 6, 15, 18, 21, 24, 30), encode them using:

 Delta encoding

 Rice code with k=3

 Elias-Fano encoding

Riferimenti

Scarica adesso ( DOC - 1 pagine - 40.50 KB )

Documenti correlati

Lifelong learning e valorizzazione dei saperi e delle competenze

Nell’ambito di tale prospettiva la Commissione Europea nel dicembre 2004 ha adottato una Deci- sione relativa all’istituzione di un “quadro unico” per la trasparenza delle

On the space complexity of DAG computations

Since it will be possible to produce computations without recalculations that evaluate −→ G V using memory space m (e.g., the bottom up execution by levels starting from the leaves),

Compute the sum of the squares of distances from the center of O to the incenters of the triangles of∆ and show that this sum is independent of

[r]

Find a basis of the image of A and show that it really is a basis

Answer: As a basis of Im A, take the first, fourth and fifth columns, so that A has rank 3. Find a basis of the kernel of A and show that it really is a basis... Does the union of

Find a basis of the image of A and show that it really is a basis

If S is not a linearly independent set of vectors, remove as many vectors as necessary to find a basis of its linear span and write the remaining vectors in S as a linear combination

Algorithm Engineering 15 June 2018

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

In view of the great relevance of the work of Kolmogorov and of its impact on the

We come now to the crucial problem that has challenged mathematicians for a couple of centuries: the accumulation of small divisors, which is indeed the most challenging part of

Guarda Sapiente senilità

Una famiglia unita e collaborativa, calorosa e attenta, dove i genitori consegnano ai figli la testimonianza coerente di una vita positiva e co- struttiva e dove i figli