Scheda di esercizi di Algoritmi e complessità con soluzioni

Un algoritmo con due cicli annidati, ciascuno eseguito n volte, ha tipicamente quale complessità?

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

Quale di questi tempi di esecuzione è polinomiale?

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

Qual è il caso base di una funzione ricorsiva?

1. ALa chiamata che usa più memoria
2. BLa prima riga della funzione
3. CUn caso a cui si risponde direttamente senza un'altra chiamata ricorsiva
4. DIl caso con l'input più grande, che viene gestito prima di qualsiasi chiamata ricorsiva

Come costruisce l'algoritmo di Prim un albero ricoprente minimo?

1. ARimuove l'arco più costoso finché non restano cicli
2. BEsegue una visita in ampiezza e conserva l'albero BFS
3. COrdina tutti gli archi per peso e aggiunge ciascuno di essi a meno che non formi un ciclo nella foresta
4. DFa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero

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

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

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 è 3
2. BIl greedy usa 3 monete; l'ottimo è 2
3. CIl greedy usa 2 monete; l'ottimo è 2
4. DIl greedy usa 4 monete; l'ottimo è 3

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

1. ALo zaino frazionario, in cui gli oggetti si possono dividere
2. BNessuna delle due varianti
3. CEntrambe le varianti
4. DLo zaino 0/1, in cui gli oggetti si devono prendere sempre interi

La moltiplicazione di Karatsuba soddisfa T(n) = 3T(n/2) + O(n). Qual è la soluzione?

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