Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale strategia di progettazione usa il merge sort?

1. AForza bruta
2. BProgrammazione dinamica
3. CScelta greedy (golosa)
4. DDivide et impera

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

1. AIl tempo impiegato su un computer lento
2. BIl tempo impiegato sull'input più piccolo
3. CIl tempo atteso su un input casuale di dimensione n
4. DIl tempo massimo impiegato su tutti gli input di dimensione n

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

1. A8 secondi
2. B4 secondi
3. C2 secondi
4. D1 secondo

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(m + n)
2. BO(mn log n)
3. CO(mn)
4. DO(2^m+n)

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

Quanti livelli ha la ricorsione del merge sort per un array di n elementi?

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

Per dimostrare che un nuovo problema X è NP-difficile, che cosa devi fare?

1. ADimostrare che X si può verificare in tempo polinomiale
2. BRidurre in tempo polinomiale X a un problema NP-difficile noto
3. CRidurre in tempo polinomiale un problema NP-difficile noto a X
4. DDimostrare che X non ha un algoritmo polinomiale per input piccoli

L'algoritmo di programmazione dinamica di Held–Karp risolve esattamente il problema del commesso viaggiatore. Qual è il suo tempo di esecuzione per n città?

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