***********************************************************
Lista di argomenti per la prova orale
***********************************************************

1. Complessità
  - Saper valutare relazioni O, omega, theta fra funzioni
  - Ricorrenze
  - Master theorem - applicazioni
2. Algoritmi di ordinamento
  - Insertion Sort
  - Merge sort
  - Quick sort
  - Counting (Pigeonhole) Sort
  - Shell sort
  - Bucket sort
  - Limite inferiore x l'ordinamento
3. Alberi
  - Definizione
  - Implementazione
  - Visita {in,pre,post}-ordine
  - Visita in ampiezza
4. Alberi binari di ricerca
  - Definizione
  - Ricerca
  - Inserimento
  - Cancellazione
  - Successore/predecessore
  - Proprieta' generali degli alberi ABR
4. Strutture dati - 1
  - Heap binari
    - Max/MinHeapify
    - BuildMax/MinHeap
    - Heapsort
  - Alberi Red-Black
    - Definizione
    - Rotazione, inserimento (solo cenni)
    - Complessità delle operazioni
  - Tabelle hash
    - Tabelle ad indirizzamento diretto
    - Funzioni hash: metodo della divisione
    - Funzioni hash: metodo della moltiplicazione
    - Inserimento e cancellazione
    - Concatenamento
    - Indirizzamento aperto
      - Ispezione lineare
      - Ispezione quadratica
      - Doppio hashing
  - Merge-Find
    - Implementazione basata su lista
    - Implementazione basata su alberi
    - Euristica sul peso
    - Euristica sul rango
    - Euristica della compressione dei cammini
	- Complessità ammortizzata
6. Grafi - parte principale
  - Definizioni principali
  - Implementazione
  - Visite in ampiezza e applicazioni
  - Visite in profondità e applicazioni
  - Ordinamento topologico
  - Componenti connesse
  - Componenti fortemente connesse
7. Grafi - algoritmi vari
  - Minimum spanning tree
    - Kruskal
    - Prim
  - Cammini minimi, singola sorgente
    - Bellman-Ford
    % Cammini minimi su DAG
    - Dijkstra
  - Cammini minimi, sorgenti multiple
    - Floyd-Warshall
    % Johnson
  - Problemi di flusso
    - Ford-Fulkerson
    - Edmonds-Karp
8. Tecniche di programmazione
  - Divide-et-impera
  - Programmazione dinamica
  - Greedy
  - Backtrack
  - Algoritmi probabilistici
9. Analisi ammortizzata
  - Metodo degli accantonamenti 
  - Metodo dell'aggregazione
  - Metodo del potenziale
10. Divide et impera
  - Moltiplicazione grandi numeri (Karatsuba)
    - Descrivere a grandi linee l'idea, non i dettagli
    - Complessità
11. Programmazione dinamica
  - Tartaglia, Fibonacci
  - Catena di moltiplicazione di matrici
    - Sottostruttura ottima
    - Definizione del problema in maniera ricorsiva
    - Complessità
  - Sottosequenza comune massimale
    - Sottostruttura ottima
    - Definizione del problema in maniera ricorsiva
    - Complessità
  - Problema dello zaino 0-1
  - Insieme indipendente di intervalli pesati
12. Algoritmi greedy
  - Compressione di Huffman
  - Problema dello zaino frazionario 
  - Problema del resto
  - Problemi di scheduling
  - Selezione delle attività
13. Backtrack
  - Enumerazione
  - Geometria computazionale
    - Algoritmo di Graham
14. Algoritmi probabilistici
  - Quicksort
  - Problema della selezione