Appello dell'estate 2014.
Domande a uno che allo scritto aveva 24:
- Parlare del quicksort, scenario al caso ottimo e al caso pessimo, relazione di ricorrenza compresa
- Versione randomizzata del quicksort: quanti passi fa?
- Spiega come ordinare in tempo lineare un array di n elementi con elementi che hanno al massimo valore n^2, usando radix sort e counting sort in un certo modo
- Dimostrare che gli alberi AVL hanno altezza logaritmica
- Come si fa la cancellazione in un albero binario di ricerca?
- Dimostrare che il problema dell'arresto è un problema indecidibile
- Trovare il limite inferiore al problema della ricerca in un array ordinato
Domande a uno che allo scritto aveva 26:
- Dimostrare il teorema fondamentale delle ricorrenze
- Come risolvere con la programmazione dinamica il problema della massima sottosequenza comune?
- Che caratteristica hanno i problemi che si ris olvono con la programmazione dinamica? e col divide et impera?
- Cosa vuol dire che un algoritmo ha complessità pseudopolinomiale? un esempio?
Altre domande:
- Dimostrare il limite inferiore di un algoritmo per confronti per il sorting ovvero che non può ordinare meglio di n lg n
alberi di Fibonacci
- Ordinamento topologico
- Problema della fermata
- Differenza tra alberi AVL e tab.HASH quando conviene uno oppure l'altro
Orale (media 26,5 dai compitini):
- Problema della Edit Distance, parlarne e risolverlo
- Studio del caso medio di QuickSort
- Algoritmo per l'ordinamento topografico e dimostrazione della correttezza
Io arrivavo con 30 al secondo scritto della sessione estiva, le domande furono le seguenti:
- Dimostrazione del master theorem
- Cicli hamiltoniani
- Parlare in generale delle classi di complessità P ed NP
Se non ricordo male mi chiese anche qualcosa sugli heap e sulla complessità pseudopolinomiale.
![Immagine](http://i.imgur.com/S2ePNn1.jpg)
![Immagine](http://i.imgur.com/zEQGNmp.jpg)
Cito
-Limite inferiore ordinamento per confronti
-Parli dell'heap sort
-Dimostrazione complessità al caso medio inserimento/modifica nelle tabelle hash con indirizzamento aperto
-Esempio di Algo su grafi che usa una PQ (Dijkstra)
-Dimostrare che la CLIQUE è NP-Completo
-Analisi al caso medio del QuickSort
-Dimostrare che il problema dell'arresto non esiste (è indecidibile)
-Ordinamento DAG, come si calcola.
-Algoritmo di Kruskal: cos'è, correttezza e complessità.
-Esempio di problema in cui il greedy invece non dà l'ottimo->prob. Zaino: complessità pseudopolinomiale (spiegare perché). La relativa versione decisionale (sì o no) è in NP-Completo, esibire certificato polinomiale.
-Dimostrare teorema fondamentale delle ricorrenze.
-Dimostrazione altezza logaritmica alberi AVL
-Come si fa cancellazione in un AVL
-Esempio di problema in cui non è necessario leggere tutto l'input-> Ricerca binaria: dimostrare che è ottima.
-Dimostrazione correttezza algoritmo di Dijkstra (dire quali sono i passi della dimostrazione e iniziarla. E parte finale)
-Esempio di problema NP-Completo e cosa significa.
Orale del 05/07/17 voto dello scritto 26:
Le domande sono state:
- Spiegare il funzionamento dell'algoritmo RandomSelect( ) per la ricerca dell'elem di rango i e analisi di complessità al caso ottimo, medio e pessimo;
- Analisi di complessità del Build-max-heap e HeapSort con dimostrazione;
- È possibile ordinare un array di dim n in tempo lineare, dove l'elem di valore massimo è n^4? Motivare la risposta;
- Dimostrare che la ricerca SENZA successo in un OPEN-HASH è 1/(1-α) al caso medio;
- Dimostrazione ricerca CON successo in un OPEN-HASH al caso medio;
- Come si risolve il problema della Clique riferito all'esercizio 5 dell'appello del 03/07/17;
- Parlare di SAT e dimostrare che è un problema NP - completo.