Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è la memoizzazione?

1. AConvertire automaticamente la ricorsione in un ciclo equivalente così da non avere bisogno dello stack delle chiamate
2. BMemorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
3. CLiberare la memoria dopo il ritorno di una funzione
4. DScrivere commenti accanto a ogni riga di codice

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

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

Qual è il tempo di esecuzione del counting sort per n interi nell'intervallo da 0 a k?

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

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

Nel problema della selezione di attività, quale regola greedy dà sempre il numero massimo di attività non sovrapposte?

1. AScegliere per prima l'attività con meno sovrapposizioni, poi ripetere con quelle compatibili
2. BScegliere l'attività che inizia prima
3. CScegliere l'attività che termina prima, poi ripetere con quelle compatibili
4. DScegliere per prima l'attività più breve

Che cosa significa che un problema ha una sottostruttura ottima?

1. AIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
2. BIl problema si può risolvere in tempo costante
3. COgni sottoproblema ha la stessa dimensione
4. DUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi

L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n^{log₂ 7}), circa n^2,81

I cammini semplici minimi si possono trovare in tempo polinomiale. Che cosa si sa del trovare il cammino semplice più lungo tra due vertici in un grafo generico?

1. AÈ indecidibile
2. BÈ NP-difficile
3. CÈ sempre risolvibile in O(V + E)
4. DSi può risolvere con l'algoritmo di Dijkstra con pesi cambiati di segno