Scheda di esercizi di Algoritmi e complessità con soluzioni

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

1. AInsertion sort
2. BQuicksort
3. CBubble sort
4. DMerge sort

Che cosa significa f(n) = Θ(g(n))?

1. Af cresce allo stesso ritmo di g, limitata superiormente e inferiormente da multipli costanti di g
2. Bf cresce strettamente più velocemente di g
3. Cf è sempre minore di g per ogni n, quindi g la limita superiormente ma mai inferiormente
4. Df cresce strettamente più lentamente di g

Che cos'è la ricorsione?

1. AUn metodo di ordinamento
2. BUn ciclo che non termina mai
3. CUn tipo di struttura dati
4. DUna funzione che chiama se stessa su input più piccoli

Nel problema della selezione di attività, quale regola greedy dà sempre il numero massimo di attività non sovrapposte?

1. AScegliere l'attività che inizia prima
2. BScegliere l'attività che termina prima, poi ripetere con quelle compatibili
3. CScegliere per prima l'attività più breve
4. DScegliere per prima l'attività con meno sovrapposizioni, poi ripetere con quelle compatibili

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Quanti livelli ha la ricorsione del merge sort per un array di n elementi?

1. ACirca n
2. BCirca √n
3. CCirca log₂ n
4. DCirca n / 2

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

1. ALa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti
2. BUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
3. COgni confronto richiede un tempo logaritmico
4. DOgni elemento deve essere confrontato almeno una volta

Quale di questi problemi di soddisfacibilità è noto per essere risolvibile in tempo polinomiale?

1. ALa soddisfacibilità dei circuiti
2. B3-SAT, in cui ogni clausola ha esattamente tre letterali
3. CSAT generale su formule in forma normale congiuntiva
4. D2-SAT, in cui ogni clausola ha al massimo due letterali