Nozioni di base

• 1 ottobre. Obiettivi formativi e organizzazione del corso. Concetti fondamentali: problema computazionale, algoritmo, modello RAM, pseudocodice, taglia dell'istanza.
• 3 ottobre. Concetti fondamentali: struttura dati. Analisi di Algoritmi: complessità e correttezza; definizione della funzione complessità ordini di grandezza (O, Omega, Theta).
• 8 ottobre. Concetti fondamentali: Ordino di grandezza o-piccolo; proprietà degli ordini di grandezza; math tools (parte bassa e alta, sommatorie notevoli); esempi (PrefixAverages quadratico e lineare); procedimento per provare limiti superiori e inferiori alla complessità ; esercizio simile a R-4.29 del testo; esercizio su InsertionSort.
• 10 ottobre. Caso di studio: algoritmo RSA. Caveat relativi all'analisi asintotica al caso pessimo. Tecniche di dimostrazione: esempio, controesempio, per assurdo, induzione. Dimostrazione della formula chiusa per F(n) (n-esimo numero di Fibonacci). Esempio di induzione fallace per provare che F(n)=0
• 11 ottobre. Analisi di correttezza: approccio generale; definizione di invariante; utilizzo di un invariante per provare la correttezza di un ciclo; esempi (arrayMax e arrayFind). Esercizi: determinazione del più lungo segmento di 1 consecutivi in una sequenza binaria; conteggio del numero di 1 in una matrice binaria con gli 1 prima degli 0 in ciascuna riga e numero di 1 non crescente con l'indice di riga.
• 15 ottobre. Esercizio: determinazione di una colonna di 0 in una matrice di interi. Algoritmi ricorsivi: definizione; esempi (LinearSum e ReverseArray); albero della ricorsione; analisi di complessità tramite lalbero della ricorsione; analisi di correttezza; relazioni di ricorrenza; esempi.
• 17 ottobre. Algoritmi ricorsivi: BinaryFib (pseudocodice, relazione di ricorrenza e prova per induzione del lower bound). Algoritmo PowerFib. Esercizi: esercizio C-5.10 del testo (element uniqueness); Esempi di domande teoriche.

Text Processing

• 17 ottobre. Definizione del Pattern Matching come problema computazionale. Notazioni. Algoritmo findBrute: pseudocodice, esempi e analisi. Esercizi: C-12.14 del testo.
• 18 ottobre. Esercizio: modifica di findBrute quando il primo carattere del pattern è diverso dagli altri. Algoritmo findKMP: idee principali; definizione di failure function; pseudocodice, esempi e analisi di correttezza.
• 22 ottobre. Algoritmo computeFailKMP: idee principali; pseudocodice; esempio; analisi di complessità e correttezza. Esercizi: ricerca di un pattern come sottostringa circolare di un testo; ricerca di tutte le occorrenze di un pattern in un testo.
• 24 ottobre: Esercizi: ricerca di tutte le occorrenze di un pattern in un testo; ricerca del più lungo prefisso di un pattern in un testo. Esempi di domande teoriche.

Ripasso di Java

• 24 ottobre: Programma stand-alone; esempio (calcolo dell'n-esimo numero di Fibonacci);
• 25 ottobre: Caratteristiche di Java e della programmazione Object-Oriented: portabilità, modularità, incapsulamento, interfacce, classi astratte, ereditarietà. Programmazione generica. Lista position-based: definizione; interfaccia; implementazione doubly-linked con accesso tramite position; Pila, e Coda.
• 31 ottobre: InsertionSort: implementazione con List e ArrayList di Java. Java Collection Framework. Iteratori (interfacce Iterator e Iterable).

Alberi

• 31 ottobre: Alberi: applicazioni; definizioni; terminologia; dimostrazione Proposizione 8.3 del testo (esercizio R-8.2); metodi dell'interfaccia Tree;
• 5 novembre: Calcolo della profondità di un nodo (algoritmi ricorsivo e iterativo); calcolo dell'altezza di un nodo e di un albero; esercizio simile a R-8.19 del testo; visite in preorder e postorder (pseudocodici, analisi ed esempi). Esercizio sul calcolo delle profondità e delle altezze di tutti i nodi di un albero;
• 7 novembre: Esercizi C-8.27 e C-8.50 del testo. Alberi binari: definizione; interfaccia. Alberi binari propri: definizione; proprietà (dal testo: Proposition 8.7 del testo, limitata alla parte sugli alberi binari propri, Proposition 8.8, Esercizi R-8.7 e R-8.8).
• 8 novembre: Alberi binari: visita inorder; Parse Tree di un'espressione in notazione infissa; algoritmo evaluateExpression; algoritmo di ricostruzione della espressione a partire dal Parse Tree. Esercizi sugli alberi binari: calcolo della heightsum; metodo preorderNext e inorderNext (da esercizio C-8.41 del testo).
• 8 novembre (bis): Esercizi sugli alberi binari: conteggio dei nodi strong (lucido 26 sugli alberi binari); dimostrazione che in un albero binario proprio m >= h+1. Esempi di domande teoriche.

Priority Queue

• 8 novembre (bis): Priority Queue: definizione; Interfacce Entry(K,V) e PriorityQueue(K,V); applicazioni reali; algoritmo per top-K pattern discovery; implementazione tramite liste (ordinate e non). Albero binario completo: definizione e relazione tra altezza e numero di nodi.
• 12 novembre: Priority Queue: heap (definizione, realizzazione tramite vettore, level numbering e sue proprietà); esercizi R-9.9, R-9.10, (variante di) R-9.13 del testo. Implementazione dei metodi della Priority Queue tramite heap su array: pseudocodice e analisi.
• 14 novembre: Ripasso per il compitino: esempio di I compitino (3); esempio di I compitino (1) (domande 1 e 3 della prima parte e esercizio 1 della seconda parte); nozione di complessità di un algoritmo.
• 15 novembre: Esercizio sulla rimozione di una entry generica da uno heap, e esercizi C-9.34 e C-9.36 del testo. Esercizio 2 da Esempio di Scritto Completo (4). Cenni sull'implementazione di alberi.
• 26 novembre: Cenni sull'implementazione Java di alberi. Caso di studio: simulazione per eventi di un ufficio postale. Costruzione di uno Heap a partire da un array con n entry: approcci top-down e bottom-up. Analisi dell'approccio top-down.
• 28 novembre: Analisi dell'approccio bottom-up. Esercizio C-9.35 del testo PriorityQueueSort: SelectionSort, InsertionSort, HeapSort come casi particolari. Implementazione di HeapSort in place. Esercizio sul calcolo della entry con la k-esima chiave più piccola.
• 29 novembre: Esercizio sulla determinazione della sequenza ordinata delle m entry con chiavi più piccole di uno Heap con n>m entry. Esempi di domande teoriche.

Mappa

• 29 novembre: Mappa: definizione e applicazioni; interfaccia Map; implementazione tramite lista doubly-linked con la complessità dei metodi get, put e remove. Tabelle Hash: ingredienti principali.
• 3 dicembre: Tabelle Hash: esempio (word count); nozione di uniform hashing; scelta dell'hash code; scelta della compression function; risoluzione collisioni tramite separate chaining; implementazione dei metodi della mappa (get(k), put(k,x) e remove(k)) e loro complessità al caso pessimo e al caso medio in funzione del load factor; rehashing; esercizi R-10.5 e R-10.9 del testo.
• 5 dicembre (prof. Vandin): Alberi Binari di Ricerca (ABR): definizione; proprietà della vista in-order; metodo TreeSearch(k,v); implementazione dei metodi della mappa (get(k), put(k,x) e remove(k)) e loro analisi.
• 10 dicembre: Esercizi: esercizio R-11.1 del testo; versione iterativa di TreeSearch; conteggio del numero di entry con chiave <=k, con e senza variabile size.
• 12 dicembre: Esercizio: algoritmo non ricorsivo per trovare la più piccola chiave positiva in un albero binario di ricerca. Multi-Way Search Tree: definizione ed esempi; Proposizione 11.2 (ed esercizio C-11.46) del testo; metodo MWTreeSearch(k,v) e implementazione di get(k). (2,4)-Tree: definizione; altezza (Proposizione 11.3 del testo). Questionario di valutazione.
• 13 dicembre: Osservazioni sui questionari. (2,4)-Tree: metodi put(k,x) con Split(u), remove(k) con Delete(e,u,alfa). Esempi.
• 17 dicembre: MultiMappa: differenze tra MultiMappa e Mappa; specifica dei metodi get(k), put(k,x) e remove(k,v); implementazione tramite Mappa+Liste. Esercizi: calcolo dell'altezza di un (2,4)-Tree; fusione di due (2,4)-Tree T e U con la massima chiave in T minore della minima chiave in U (con stessa altezza e altezze differenti). Esempi di domande teoriche.

Grafi

• 17 dicembre: Definizione di grafo; terminologia; esempi applicativi.
• 19 dicembre: Concetti fondamentali (cammino, ciclo, grafo connesso, subgraph, spanning subgraph, alberi (radicati, liberi e loro equivalenza), spanning tree/forest); proprietà dei grafi (Proposizioni 14.8, 14.10, 14.11 ed esercizio C-14.34 del testo); rappresentazione di grafi (strutture di base L_E e L_V, liste di adiacenza, matrice di adiacenza); nozione di visita; algoritmo DFS (pseudocodice).
• 20 dicembre: Algoritmo DFS: analisi; visita di tutto il grafo; applicazioni (connettività, spanning tree, s-t reachability, ciclicità).
• 7 gennaio: Esercizi: soluzione del problema del labirinto tramite DFS; aggiunta di K-1 archi per rendere connesso un grafo con K componenti connesse. Algoritmo BFS (pseudocodice e analisi); Proposizione 14.16 del testo; complessità di BFS; applicazioni (cammino minimo e ciclicità). Esercizio: massima separazione tra due vertici (ad es. profili nel grafo di Facebook).
• 9 gennaio: Esercizi: calcolo del numero di coppie di vertici raggiungibili; upper bound sulla taglia dei livelli della BFS di un grafo regolare di grado c; Esercizio C-14.49 di [GTG14]. Esempi di domande teoriche.

Ordinamento

• 9 gennaio: Introduzione al problema dell'ordinamento. Definizione di algoritmo basato su confronti. MergeSort (algoritmo, analisi di Merge, analisi di MergeSort tramite l'albero della ricorsione).
• 10 gennaio: Analisi di MergeSort tramite l'albero della ricorsione per n potenza di 2 ed n generale). Esecizio sulla fusione di k sequenze ordinate. QuickSort: strategia generale; pseudocodice in-place (QuickSortInPlace); complessità di partition; esempi.
• 14 gennaio: QuickSortInPlace: analisi di complessità tramite albero della ricorsione. Distinzione tra algoritmi probabilistici e deterministici e definizione dell'analisi di complessità in alta probabilità e in media per un algoritmo probabilistico. Randomized QuickSort: algoritmo; complessità probabilistica (senza prova). Esercizi: modifica di QuickSortInPlace per renderlo fedele alla strategia L-E-G nel caso di chiavi non distinte (Esercizio C-13.33 in [GTG14]); modifica di Merge per determinare la taglia dell'intersezione di due sequenze ordinate con chiavi distinte.
• 16 gennaio: Esercizio C-13.42 del testo. InsertionSort: algoritmo in place; analisi in funzione della taglia dell'input e del numero di inversioni. Lower bound sulla complessità di un algoritmo quasliasi algoritmo di ordinamento basato su confronti (senza prova). BucketSort: algortimo e analisi di complessità. Nozione di ordinamento stabile.
• 17 gennaio: Radix Sort: algoritmo; analisi di complessità. e analisi di correttezza. Esercizi: C-13.39; C-13.40; lconteggio delle chiavi frequenti (Esempio di II Compitino (3)). Esempi di domande teoriche