Scheda di esercizi di Algoritmi e complessità con soluzioni

Quali sono i tre passi di un algoritmo divide et impera?

1. ADividi, risolvi (impera), combina
2. BIndovina, verifica, ripeti
3. COrdina, cerca, restituisci
4. DLeggi, calcola, scrivi

Che cosa significa che un'operazione ha tempo O(1)?

1. ARichiede sempre esattamente un secondo
2. BPuò essere eseguita una sola volta
3. CIl suo tempo di esecuzione non cresce con la dimensione dell'input
4. DElabora esattamente un elemento per ogni secondo di tempo di esecuzione

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

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

Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?

1. AI cammini minimi tra tutte le coppie di vertici in O(V³)
2. BI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
3. CUn ordinamento topologico in O(V²)
4. DUn albero ricoprente minimo in O(E log V)

Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?

1. AIl greedy usa 3 monete; l'ottimo è 2
2. BIl greedy usa 4 monete; l'ottimo è 3
3. CIl greedy usa 3 monete; l'ottimo è 3
4. DIl greedy usa 2 monete; l'ottimo è 2

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?

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

Quale limite è corretto per log(n!)?

1. AΘ(n log n)
2. BΘ(log n)
3. CΘ(n²)
4. DΘ(n)

L'insertion sort richiede O(n) su un input ordinato. Questo contraddice il limite inferiore Ω(n log n) per l'ordinamento per confronti?

1. ANo, perché l'insertion sort non è un ordinamento per confronti
2. BNo, il limite inferiore si applica al caso peggiore su tutti gli input, non a ogni input
3. CSì, quindi il limite inferiore è sbagliato
4. DSì, ma solo per array più corti di 100