Scheda di esercizi di Algoritmi e complessità con soluzioni

Un algoritmo O(n) impiega 3 secondi per n = 1 milione. Circa quanto impiega per n = 2 milioni?

1. A12 secondi
2. B9 secondi
3. C3 secondi
4. D6 secondi

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. AInsertion sort
2. BMerge sort
3. CBubble sort
4. DQuicksort

La complessità spaziale misura:

1. ALe dimensioni fisiche del computer
2. BIl numero di righe di codice
3. CLa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input
4. DLo spazio su disco del file del programma una volta compilato

La visita in ampiezza (BFS) su un grafo non pesato trova:

1. AL'albero ricoprente minimo
2. BUn ordinamento topologico in tutti i grafi
3. CI cammini minimi in numero di archi dal nodo di partenza
4. DI cammini minimi in grafi che contengono archi con peso negativo

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

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

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)

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(2^n²)
2. BO(n³)
3. CO(n² 2ⁿ)
4. DO(n!)

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

1. APerché n è sempre piccolo
2. BPerché funziona solo per W = 0
3. CPerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
4. DW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W