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. BOrdina, cerca, restituisci
3. CLeggi, calcola, scrivi
4. DIndovina, verifica, ripeti

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

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

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

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

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

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

Un algoritmo greedy (goloso):

1. AUsa solo la ricorsione
2. BFornisce sempre la soluzione ottima
3. CProva ogni soluzione possibile
4. DCompie la scelta localmente migliore a ogni passo

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. AAl massimo il doppio della dimensione di una copertura dei vertici minima
2. BSempre una copertura dei vertici minima
3. CDi qualità ignota rispetto all'ottimo
4. DAl massimo log n volte il minimo

L'ordinamento topologico è possibile solo per:

1. AGrafi con pesi negativi
2. BGrafi completi
3. CGrafi orientati aciclici (DAG)
4. DGrafi non orientati