Domande colloquio integrativo

[mara]

Dopo il passaggio dal vecchio al nuovo ordinamento, ho le domande di due orali con la prof Pisanti di studenti che avevano dato Programmazione 1 e Lab per il riconoscimento di Programazione e Algoritmi.

Colloquio integrativo algoritmi (6CFU)

Argomenti:
* Nozioni di Algoritmo e di Problema.
* Complessità computazionale: caso pessimo e caso medio.
* Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
* Divide-et-impera, relazioni di ricorrenza e teorema principale.
* MergeSort: algoritmo e sua analisi.
* QuickSort: algoritmo e sua analisi
* Dizionari: tabelle hash e alberi binari di ricerca (senza dimostrazioni)

Orale 1:
Dato un algoritmo ricorsivo: [in allegato al post]
- Scrivere la relazione di ricorrenza
- Risolverla con il teorema dell’esperto
Dato un albero:
- dire se è un ABR
- ricercare un elemento
- qual’è il costo massimo della ricerca
- Scrivere il risultato della visita anticipata
Merge Sort
- Spiegare a parole come funziona
- Scrivere la relazione di ricorrenza
- Risolverla con il teorema dell’esperto
- Dire se è ottimo
Limiti inferiori di un problema
- Come si può trovare? (Dimensione, eventi contabili, albero di decisione)
- Dimostrare il limite inferiore per il problema dell’ordinamento [lode]
Tabelle hash
- Cos’è una tabella hash
- Come funziona il concatenamento

Orale 2:
*Costo di uno pseudocodice.
*Algoritmo ricorsivo che trova la dimensione di un albero. (+ Costo)
*Algoritmo ricorsivo che trova il numero delle foglie di un albero. (+Costo)
*Parlare di MergeSort+costo+applicare teorema esperto su T(n).
*Tabelle hash
*Che tipo di ashing abbiamo visto.
*Cosa sono le collisioni.
*Come si trova il limite inferiore.

[mara]

Riassunti per colloquio integrativo dei seguenti capitoli:

[CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, Terza edizione, 2010.
Cap 1.
Cap 2: 2.1, 2.2, 2.3.
Cap 3.
Cap 4: 4.2, 4.5, 4.6.1.
Cap 7: 7.1, 7.2, 7.3, 7.4.2.
Cap 8: 8.1.
Cap 11: 11.1, 11.2, 11.3, 11.3.1, 11.3.2, 11.4
[CGGR]: P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di dati e algoritmi: progettazione, analisi e programmazione (seconda edizione). Pearson, 2012
Par.3.8 : 3.8.1, 3.8.2, 3.8.3 (vedi materiale lezioni AA 2019-2020 per i pdf dei singoli paragrafi).