Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale notazione descrive un limite superiore della crescita?

1. AOmega grande (Big Omega)
2. BTheta grande (Big Theta)
3. CO grande (Big O)
4. DOmega piccolo (little omega)

Un algoritmo O(n²) impiega 1 secondo per n = 1000. Circa quanto impiega per n = 2000?

1. A1 secondo
2. B2 secondi
3. C4 secondi
4. D8 secondi

Qual è la complessità temporale della visita in profondità (DFS) su un grafo memorizzato con liste di adiacenza?

1. AO(V²)
2. BO(V + E)
3. CO(V × E)
4. DO(E log V)

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

1. ACirca 20
2. BCirca 500,000
3. CCirca 1,000
4. DCirca 100

La programmazione dinamica è utile quando un problema presenta:

1. AUn unico ciclo
2. BSolo input casuali
3. CNessun sottoproblema, quindi si risolve in un solo passo
4. DSottoproblemi sovrapposti e sottostruttura ottima

Qual è la complessità temporale del calcolo dell'n-esimo numero di Fibonacci con una tabella bottom-up?

1. AO(n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(log n)

Quale affermazione sulla selezione del k-esimo elemento più piccolo di un array non ordinato è corretta?

1. AIl quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore
2. BIl quickselect richiede O(log n) nel caso peggiore, perché ricorre su un solo lato del pivot
3. CLa selezione è possibile solo in O(n²)
4. DLa selezione richiede sempre Ω(n log n) perché richiede un ordinamento

Usando il teorema dell'esperto (master theorem), T(n) = 8T(n/2) + O(n²) ha come soluzione:

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n² log n)
4. DΘ(n³)