Scheda di esercizi di Algoritmi e complessità con soluzioni

Accedere a un elemento di un array tramite indice richiede:

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

Qual è la complessità temporale della visita in profondità (DFS) su un grafo memorizzato con liste di adiacenza?

1. AO(E log V)
2. BO(V × E)
3. CO(V + E)
4. DO(V²)

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

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

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

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

Che cosa seguirebbe se qualcuno trovasse un algoritmo in tempo polinomiale per un problema NP-completo?

1. ATutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
2. BOgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
3. CSolo quel problema passerebbe in P
4. DIl problema della fermata diventerebbe decidibile

Usando il teorema dell'esperto (master theorem), T(n) = 8T(n/2) + O(n²) ha come soluzione:

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