Algoritmi e strutture dati - Esercizi

Algoritmi e Strutture Dati

&

Laboratorio di Algoritmi e Programmazione

— Appello del 14 Gennaio 2009 —

Esercizio 1 - ASD

Si risolvano le seguenti ricorrenze, giustificando la risposta.

√

n 2

• T (n) = 9T ( ) + 3n + 2 n

3

52 n

• T (n) = T ( ) + n

2

Soluzione √

2 2 2

• Poiché lg 9 = 2 e f (n) = 3n + 2 n = Θ(n ) siamo nel caso 2 del MT e la soluzione è T (n) = Θ(n lg n).

3 5

52 5 lg −²

• Poiché lg > 1 esiste ² > 0 tale che 1 = lg − ². Quindi f (n) = n = O(n ). Siamo nel caso 1 del MT e

2 2

2 2 2

5

lg ).

la soluzione è T (n) = Θ(n 2 2

Esercizio 2 - ASD

Date le seguenti procedure A e B, si determini la complessità asintotica della procedura A(n) su input n.

A(n)

1 s ← 0

2 for i ← 1 to n

3 do s ← s + B(i)

4 return s

B(m)

1 s ← 0

2 for j ← 1 to m

3 do s ← s + 1

4 return s

Soluzione

La complessità di B(i) è lineare in i pertanto ad ogni iterazione del ciclo la terza istruzione di A ha costo ki per una

P n 2

qualche costante k. Sommando su tutti i valori che assume la variabile i otteniamo T (n) = (ki) = Θ(n )

A i=1

Esercizio 3 - ASD

Scrivere un algoritmo che dato un albero binario di ricerca T , bilanciato e contenente chiavi tutte distinte, e due chiavi

k < k restituisce true se e solo se T soddisfa anche la seguente proprietà:

1 2

- per ogni nodo x di T se key[x] = k allora non esiste alcun nodo y 6 = x in T tale che k < key[y] < k .

1 1 2

Dire qual è la complessità dell’algoritmo rispetto al numero delle chiavi memorizzate nell’albero e spiegare perché è

corretto.

Soluzione

Precondizione: x è la radice di un BST bilanciato.

Postcondizione: L’algoritmo risponde true se l’albero radicato in x gode della proprietà data, false altrimenti.

check(x, k1, k2)

1 z ← bstsearch(x, k1)

2 if ((z = NIL) ∨ (succ(z) = NIL)

3 then return true

4 else return (key[succ(z)] ≥ k2)

Correttezza: Se la chiave k non compare nell’albero (la bstsearch ritorna NIL) allora la condizione è soddisfatta;

1

idem se compare ma è la più grande (succ(z) ritorna NIL); altrimenti (compare e non è la più grande), è sufficiente

verificare che la chiave del successore di z sia maggiore o uguale a k . Infatti la proprietà BST ci assicura che tutti i

2

predecessori di un nodo hanno chiave minore o uguale a quella del nodo mentre i suoi successori hanno chiave maggiore

o uguale.

Complesità: La complessità è logaritmica nel numero delle chiavi. Infatti sia la ricerca di una chiave che l’individua-

zione del successore sono operazioni lineari nell’altezza dell’albero, e l’albero è bilanciato.

Esercizio 4 - ASD

Si disegni un albero R/B che contiene le seguenti chiavi: 6, 15, 8, 2, 24, 56, 3, 43, 12, 4, 7. Lo si trasformi poi in un

albero 2-3-4.

Soluzione

Una possibile soluzione è la seguente.

8 B

/ \

4 R 24 R

/ \ / \

3 B 7 B 15 B 56 B

/ / / /

2 R 6 R 12 R 43 R

4,8,24

/ / \ \

2,3 6,7 12,15 43,56

Esercizio 5 - ASD

Si sviluppi un algoritmo che, dati un albero generale T e un intero positivo k > 0, conta il numero di nodi di grado k

in T . Si supponga che l’albero generale sia rappresentato tramite gli attributi: fratello e figlio. (Ricordiamo che

il grado di un nodo di un albero è pari al numero dei suoi figli.)

Soluzione

contagrado(x, k)

1 if (x = NIL)

2 then return 0

3 else z ← f iglio[x]

4 n ← 0

5 while (z 6 = NIL)

6 do n ← n + 1

7 z ← f ratello[z]

8 if (n = k)

9 then return 1 + contagrado(f ratello[x], k) + contagrado(f iglio[x], k)

10 else return contagrado(f ratello[x], k) + contagrado(f iglio[x], k)