Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. AQuicksort
2. BMerge sort
3. CBubble sort
4. DInsertion sort

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

1. ACirca n
2. BCirca log₂ n
3. CCirca n / 2
4. DCirca n²

Quale di questi tempi di esecuzione è polinomiale?

1. AO(nⁿ)
2. BO(n!)
3. CO(2ⁿ)
4. DO(n³)

La ricorrenza T(n) = 2T(n/2) + O(n) ha come soluzione:

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(mn log n)
2. BO(2^m+n)
3. CO(m + n)
4. DO(mn)

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. AGli array hanno accesso O(n)
2. BLe chiavi devono prima essere ordinate
3. CMolte chiavi possono collidere nello stesso bucket
4. DLe funzioni hash sono lente

Come si classifica il problema del commesso viaggiatore?

1. AÈ in P perché l'algoritmo di Dijkstra lo risolve visitando ogni città una sola volta
2. BÈ indecidibile
3. CLa versione decisionale è NP-completa e la versione di ottimizzazione è NP-difficile
4. DLa versione decisionale è in P ma quella di ottimizzazione è NP-completa