PROGRAMMA ORIENTATIVO DEL CORSO DI
ALGORITMI E STRUTTURE DAI A.A. 2007-2008

Analisi e progetto di algoritmi, tecnica divide et impera, merge-sort: Cap.1 e 2.

Ordine di grandezza delle funzioni:  Cap.3:
       Notazioni asintoiche Theta O-grande, 
       Omega: 3.1 (no notazione o-piccolo e omega-piccolo) 

Ricorrenze Cap.4
       Il metodo di sostituzione: 4.1, Il metodo dell'albero di ricorsione 4.2. 
       Il Master Theorem (lucidi)

Heapsort Cap.6
        Heap 6.1
        Conservare le proprieta' dell'Heap 6.2
        Costruire un heap 6.3
        L'algoritmo heap-sort 6.4
        Code con priorita' 6.5

Quicksort Cap. 7 (secondo la partizione di Hoare in problema 7-1 e lucidi)
Ordinamenti in tempo lineare: Cap. 8
        Counting sort 8.2

Strutture dati elementari: Cap. 10 
	10.1 Stack e code
	10.2 Liste concatenate

Hashing Cap. 11
	11.1 Tavole a indirizzamento diretto
	11.2 Tavole hash
	11.3 Funzioni hash (escluso "progettare una classe universale di funzioni hash
	11.4 Indirizzamento aperto (escluso "Hashing perfetto")
	I teoremi senza dimostrazioni

Alberi binari di ricerca Cap. 12
	Tutto fino a 12.3 incluso

Alberi rosso-neri Cap. 13
	13.1 Proprieta'
	13.2 Rotazioni
	Cenni sull'inserimento

B-alberi Cap.18 (cenni)
	18.1 Introduzione
	18.2 Definiizione dei B-alberi

Algoritmi sulle matrici e soluzione dei sistemi d'equazioni lineari Cap. 28 (28.1, 28.2, 28.3)
	(Vedi dispensa 09-algebra-lineare)

Algoritmi elementari per grafi Cap. 22
	22.1 Rappresentazione dei grafi
	22.2 Visita in ampiezza (no alberi di visita in ampiezza)
	22.3 Visita in profondita' (no proprieta' della visita in profondita', no classificazione degli archi)
	22.4 Ordinamento topologico.


-Esercizi e integrazioni sui lucidi presentati in aula durante le lezioni e le esercitazioni
	
-Testo di riferimento: T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein 
Introduzione agli Algoritmi e alle Strutture Dati 
McGraw-Hill (seconda edizione)