Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che prova tutte le possibili soluzioni candidate
2. BUn algoritmo che tira a indovinare una risposta a caso
3. CUn algoritmo che gira su molti processori
4. DUn algoritmo che usa sempre la ricorsione

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

1. ADividi, risolvi (impera), combina
2. BOrdina, cerca, restituisci
3. CIndovina, verifica, ripeti
4. DLeggi, calcola, scrivi

Che cos'è la memoizzazione?

1. ALiberare la memoria dopo il ritorno di una funzione
2. BMemorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
3. CScrivere commenti accanto a ogni riga di codice
4. DConvertire automaticamente la ricorsione in un ciclo equivalente così da non avere bisogno dello stack delle chiamate

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

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

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

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. ALe chiavi devono prima essere ordinate
2. BMolte chiavi possono collidere nello stesso bucket
3. CLe funzioni hash sono lente
4. DGli array hanno accesso O(n)

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

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