Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di questi tempi di esecuzione è polinomiale?

1. AO(n!)
2. BO(nⁿ)
3. CO(2ⁿ)
4. DO(n³)

Quale notazione descrive un limite superiore della crescita?

1. AO grande (Big O)
2. BOmega piccolo (little omega)
3. CTheta grande (Big Theta)
4. DOmega grande (Big Omega)

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

La visita in ampiezza (BFS) su un grafo non pesato trova:

1. AI cammini minimi in grafi che contengono archi con peso negativo
2. BUn ordinamento topologico in tutti i grafi
3. CL'albero ricoprente minimo
4. DI cammini minimi in numero di archi dal nodo di partenza

Perché molte routine di ordinamento delle librerie passano all'insertion sort per sottoarray molto piccoli?

1. AL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati
2. BL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi
3. CL'insertion sort è O(n log n) nel caso peggiore
4. DGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

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

I cammini semplici minimi si possono trovare in tempo polinomiale. Che cosa si sa del trovare il cammino semplice più lungo tra due vertici in un grafo generico?

1. AÈ sempre risolvibile in O(V + E)
2. BÈ indecidibile
3. CÈ NP-difficile
4. DSi può risolvere con l'algoritmo di Dijkstra con pesi cambiati di segno

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

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