Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

Quale di queste cresce più lentamente quando n diventa grande?

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

Che cosa descrive il tempo di esecuzione nel caso peggiore di un algoritmo?

1. AIl tempo impiegato sull'input più piccolo
2. BIl tempo impiegato su un computer lento
3. CIl tempo massimo impiegato su tutti gli input di dimensione n
4. DIl tempo atteso su un input casuale di dimensione 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(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

1. AO(n log n + k log n)
2. BO(nk)
3. CO(k n log n)
4. DO(n + k)

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

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

Che cosa seguirebbe se qualcuno trovasse un algoritmo in tempo polinomiale per un problema NP-completo?

1. ASolo quel problema passerebbe in P
2. BIl problema della fermata diventerebbe decidibile
3. CTutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
4. DOgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP

Come si classifica il problema del commesso viaggiatore?

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