Programma (Orientativo)

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

• Design di Algoritmi
  • Divide & Impera: MergeSort.
  • Analisi di MergeSort.
  • Ricorrenze
    • sostituzione.
    • albero di ricorsione.
    • master theorem.
  • 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 e componenti biconnesse.
  • Algoritmo di Dijkstra per i cammini minimi.
  • Alberi ricoprenti minimi ? (opzionale, non credo ce la faremo)
    • Prim.
    • Kruskal.

• Analisi Probabilistica ed Algoritmi Randomizzati
  • Il paradosso dei compleanni.
  • QuickSort.
  • Coupon collector.