Algoritmi e strutture dati - esercizi vari

Algoritmi e Strutture Dati

&

Laboratorio di Algoritmi e Programmazione

— Appello del 14 Gennaio 2009 —

Esercizio 1 - ASD

Provare la verità o la falsità di ciascuna delle seguenti affermazioni.

√

n 2

2 3

• n è nella classe Θ(n )

) + 3n + 2

La soluzione della ricorrenza T (n) = 5T ( 3

2 2

• Ω(n lg n) + n = O(n ) √ 2 2

• La soluzione della ricorrenza T (n) = 2T ( n) + 3n è nella classe Θ(n )

Esercizio 2 - ASD

Discutere la correttezza di ciascuna delle seguenti affermazioni. Dimostrare formalmente la validità delle risposte date.

1. La complessità asintotica dell’algoritmo di ricerca di una chiave in un albero R/B con n nodi è Θ(lg n).

2. La complessità asintotica dell’algoritmo di ricerca di una chiave in un albero BST con n nodi è Ω(lg n).

3. La complessità asintotica dell’algoritmo di ricerca di una chiave in un min-heap binario con n nodi è Θ(n).

4. Esistono alberi R/N che hanno tutti i nodi neri.

5. Possiamo trasformare un albero R/B con n nodi in un min-heap con complessità asintotica Θ(n).

Esercizio 3 - ASD

Diciamo che T è un interval BST se è un BST a chiavi intere che soddisfa la seguente proprietà: per ogni intero k, se

le chiavi k e k + 2 sono in T allora anche la chiave k + 1 è in T .

Proporre un algoritmo che verifica se un dato BST a chiavi intere è un interval BST.

Dire qual è la complessità dell’algoritmo e spiegare perché è corretto.

Esercizio 4 - ASD

Si realizzi una operazione k, P ) che soddisfa la seguente specifica:

rimuovi(A, ≤

Precondizione: A è un array che rappresenta un max-heap di dimensione a chiavi intere; 0 < k 100

heapsize[A]

e P > 0 sono due costanti.

Postcondizione: L’algoritmo restituisce un nuovo array A che rappresenta il max-heap ottenuto eliminando da quello

iniziale i k più grandi elementi di A maggiori di P oppure tutti gli elementi di A maggiori di P nel caso vi siano in A

meno di k elementi maggiori di P .

Dire qual è la complessità dell’algoritmo rispetto alla dimensione iniziale di A e spiegare perché è corretto.