Scheda di esercizi di Algoritmi e complessità con soluzioni

Un algoritmo O(n) impiega 3 secondi per n = 1 milione. Circa quanto impiega per n = 2 milioni?

1. A3 secondi
2. B6 secondi
3. C9 secondi
4. D12 secondi

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

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

Quale di queste cresce più lentamente quando n diventa grande?

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

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²)

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

1. AI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
2. BIl merge sort è già O(n)
3. CLa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
4. DIl merge sort non ha una struttura ricorsiva

Che cosa significa che un problema ha una sottostruttura ottima?

1. AIl problema si può risolvere in tempo costante
2. BIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
3. CUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
4. DOgni sottoproblema ha la stessa dimensione

Quale definizione della classe NP è corretta?

1. AProblemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato
2. BProblemi che nessun algoritmo può risolvere
3. CProblemi che non sono polinomiali
4. DProblemi che non si possono risolvere in tempo polinomiale

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ì, ma solo per array più corti di 100
4. DSì, quindi il limite inferiore è sbagliato