Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Quale notazione descrive un limite inferiore alla crescita?

1. AΘ (Theta grande)
2. Bo (o piccolo)
3. CO (O grande)
4. DΩ (Omega grande)

Qual è il tempo di esecuzione del counting sort per n interi nell'intervallo da 0 a k?

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

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(2^m+n)
2. BO(m + n)
3. CO(mn)
4. DO(mn log n)

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

1. ACirca 500,000
2. BCirca 100
3. CCirca 20
4. DCirca 1,000

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

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

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. AControlla se qualche arco ha peso negativo
2. BEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze
3. CDopo V − 1 turni controlla se qualche arco può ancora essere rilassato
4. DConta i cicli con una visita in profondità

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

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