Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di questi tempi di esecuzione è polinomiale?

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

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. CScrivere commenti accanto a ogni riga di codice
4. DLiberare la memoria dopo il ritorno di una funzione

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

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

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

Quale algoritmo trova i cammini minimi da una sorgente in un grafo con pesi degli archi non negativi?

1. AAlgoritmo di Kruskal
2. BBellman-Ford è necessario in tutti i casi
3. CVisita in profondità (DFS)
4. DAlgoritmo di Dijkstra

Quale affermazione sulla notazione o piccolo è corretta?

1. An² = o(n)
2. Bn = o(n), perché ogni funzione è o piccolo di se stessa
3. Cn = o(n²), ma n non è o(n)
4. D2n = o(n), perché 2n cresce lentamente

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È sempre risolvibile in O(V + E)
2. BÈ indecidibile
3. CSi può risolvere con l'algoritmo di Dijkstra con pesi cambiati di segno
4. DÈ NP-difficile