Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

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

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

Quanto vale log₂ 1024?

1. A32
2. B10
3. C12
4. D512

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ASì, ma solo se n è minore di 100
2. BNo, perché per n grande n³ è minore di n²
3. CSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
4. DNo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione

Perché molte routine di ordinamento delle librerie passano all'insertion sort per sottoarray molto piccoli?

1. AGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi
2. BL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati
3. CL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi
4. DL'insertion sort è O(n log n) nel caso peggiore

Che cosa misura l'analisi ammortizzata?

1. AIl costo di un algoritmo sull'input migliore
2. BIl costo medio per operazione su una sequenza di operazioni nel caso peggiore
3. CIl costo atteso su input casuali
4. DIl costo della singola operazione più costosa in un punto qualsiasi della sequenza

Che cosa ha stabilito il teorema di Cook–Levin?

1. AP è diverso da NP
2. BIl problema della fermata è indecidibile
3. CIl problema della soddisfacibilità booleana (SAT) è NP-completo
4. DOgni problema NP si può risolvere in tempo esponenziale

Quale algoritmo trova un albero ricoprente minimo aggiungendo ripetutamente l'arco più economico che non forma un ciclo?

1. AFloyd-Warshall
2. BAlgoritmo di Prim a partire da un nodo
3. CAlgoritmo di Kruskal
4. DAlgoritmo di Dijkstra