Diario delle lezioni (Algoritmi I, Informatica, A.A. 2008-2009)

• 22 Sep - Introduzione al corso. Un esempio "giocattolo": i numeri di Fibonacci. Algoritmo ricorsivo, albero della ricorsione.

• 25 Sep - Analisi algoritmo ricorsivo. Algoritmi iterativi. Occupazione di memoria. Notazione asintotica.

• 29 Sep - Algoritmo basato su potenze di matrice. Soluzione ricorrenze per iterazione. Un nuovo esempio: ricerca di duplicati.

• 02 Oct - Esercitazione: Fibonacci e ricerca dei duplicati ricorsiva

• 06 Oct - Caso peggiore e migliore. Analisi ricerca di duplicati. Insertion e selection sort: pseudocodice e correttezza.

• 09 Oct - Tempo di esecuzione Insertionsort e Selectionsort. Mergesort (con analisi).

• 13 Oct - Heap: altezza, vettore posizionale, fixHeap, cancellazione max, costruzione. Esercizi notazione asintotica.

• 16 Oct - Esercitazione: Bubblesort iterativo e ricorsivo, variante mergesort

• 20 Oct - Heapsort. Analisi heapify. Teorema master: enunciato ed esempi d'uso.

• 23 Oct - Esercitazione annullata per assemblea di studenti e docenti (14 - 18 Aula I NEC)

• 27 Oct - Sospensione didattica per protesta Legge 133

• 30 Oct - Sospensione didattica per protesta Legge 133

• 3 Nov - Sospensione didattica per protesta Legge 133

• 6 Nov - Esercitazione: Relazioni di ricorrenza, ricerca binaria, analisi fixheap

• 10 Nov - Metodo di sostituzione. Quicksort: partition in loco, analisi caso peggiore e migliore, intuizione caso medio.

• 13 Nov - Esercitazione: esercizio 2.9, problemi 2.9 e 2.10, esercizio 4.12, esercizio 7 assegnato in classe

• 17 Nov - Lower bound ordinamento. Ordinamenti lineari: integerSort e bucketSort. Problema 4.12.

• 20 Nov - Esercizi di preparazione alla prova intermedia.

• 24 Nov - Ore cedute al corso di Laboratorio di Sistemi Operativi

• 27 Nov - Prova Intermedia

• 1 Dec - ABR: alberi binari di ricerca. Rappresentazioni di alberi: indicizzate e collegate.

• 4 Dec - Esercitazione: soluzioni prova intermedia

• 8 Dec - Festività Immacolata Concezione

• 11 Dec - Alberi AVL: definizioni, delimitazione altezza, rotazioni, operazione insert.

• 15 Dec - AVL: operazione delete. Visite di alberi: visita generica, in profondità, per livelli. Esercizi.

• 18 Dec - Definizione di grafo. Grafi orientati. Cammini e cicli. Rappresentazioni in memoria.

• 8 Jan 2009 - Visite di grafi non orientati: visita generica, analisi tempo di esecuzione, visita BFS, proprietà dell'albero BFS.

• 12 Jan 2009 - Visita DFS ricorsiva e iterativa, proprietà dell'albero DFS. Visite di grafi orientati. Calcolo componenti connesse.

• 15 Jan 2009 - Esercitazione: Esercizi su grafi e alberi AVL. Grafi bipartiti.

• 19 Jan 2009 - Esercizi di preparazione all'esame: grafi e alberi AVL.