Programma (Svolto)

• Problemi, Algoritmi, Efficienza
• InsertSort
  • Invarianti di ciclo e correttezza.
  • Analisi del tempo di calcolo di InsertSort.
  • Analisi caso peggiore, caso medio, ordini di grandezza.

• Ordini di Grandezza e Notazione Asintotica
  • Definizione delle notazioni $O(f(n)),o(f(n)),\Omega(f(n)),\omega(f(n))$ e $\Theta(f(n))$ per funzioni definitivamente non negative (come date nel Cormen).
  • Algebra e proprità delle notazioni asintotiche introdotte.
  • Impiego e pratica delle notazioni asintotiche introdotte.

• Design di Algoritmi
  • Divide & Impera: MergeSort.
  • Analisi di MergeSort.
  • Algoritmi Ricorsivi e Ricorrenze.

• Ricorrenze
  • Sostituzione.
  • Albero di ricorsione.
  • Master theorem.
  • Impiego di ricorrenze e pratica nel risolverle.

• Lower Bounds
  • Dimensioni dell'input e dell'output.
  • Lower bound per l'ordinamento.
  • Lower bound per il merging di due liste ordinate.

• Esempi di design Divide & Impera
  • Ricerca del mediano in tempo lineare.
  • Fast matrix multiplication.

• Strutture Dati Astratte
  • Pile.
  • Liste.
  • Code di priorità e heaps (binari).
  • HeapSort.

• Algoritmi su Grafi
  • Rappresentazione di grafi.
  • BFS e componenti connesse.
  • DFS: Trémaux visita un labirinto.
  • Algoritmo di Dijkstra per i cammini minimi.
  • Alberi ricoprenti minimi ed algoritmo di Prim.

• Analisi Ammortizzata
  • Esempio di un contatore su cifre binarie.
  • Esempio di una pila con MultiPop.
  • Analisi aggregata.
  • Metodo degli accantonamenti.
  • Metodo del potenziale.

• Binomial Heaps
  • Descrizione della struttura dati e relative invarianti.
  • Descrizione delle singole operazioni.
  • Analisi del caso peggiore per le singole operazioni.

• Fibonacci Heaps
  • Descrizione della struttura dati e relative invarianti.
  • Descrizione delle singole operazioni.
  • Analisi ammortizzata per le singole operazioni.
  • Fibonacci heaps ed algoritmo di Dijkstra.
  • Fibonacci heaps ed algoritmo di Prim.

• Analisi Probabilistica ed Algoritmi Randomizzati
  • Il paradosso dei compleanni.
  • QuickSort e relativa analisi (come da Cormen 2001).
  • Coupon collector.