Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa richiede la ricerca binaria al suo input?

1. AL'array deve essere ordinato
2. BLa lunghezza dell'array deve essere una potenza di due
3. CL'array non deve avere più di 1000 elementi
4. DL'array deve contenere solo numeri positivi

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

1. ABubble sort
2. BHeap sort
3. CMerge sort
4. DQuicksort

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

1. AQuicksort
2. BInsertion sort
3. CBubble sort
4. DMerge sort

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ANo, perché per n grande n³ è minore di n²
2. BSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
3. CNo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione
4. DSì, ma solo se n è minore di 100

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

1. ALa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
2. BI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
3. CIl merge sort non ha una struttura ricorsiva
4. DIl merge sort è già O(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 è 2
2. BIl greedy usa 4 monete; l'ottimo è 3
3. CIl greedy usa 2 monete; l'ottimo è 2
4. DIl greedy usa 3 monete; l'ottimo è 3

Per dimostrare che un nuovo problema X è NP-difficile, che cosa devi fare?

1. ARidurre in tempo polinomiale X a un problema NP-difficile noto
2. BDimostrare che X si può verificare in tempo polinomiale
3. CDimostrare che X non ha un algoritmo polinomiale per input piccoli
4. DRidurre in tempo polinomiale un problema NP-difficile noto a X

Che cosa ha stabilito il teorema di Cook–Levin?

1. AP è diverso da NP
2. BIl problema della soddisfacibilità booleana (SAT) è NP-completo
3. CIl problema della fermata è indecidibile
4. DOgni problema NP si può risolvere in tempo esponenziale