Nozioni di base

• 8 ottobre. Obiettivi formativi e organizzazione del corso. Concetti fondamentali: problema computazionale, algoritmo, modello RAM.
• 9 ottobre. Concetti fondamentali: taglia dell'istanza, struttura dati, pseudocodice. Esercizio: formalizzazione del problema del massimo segmento di 1 in una stringa binaria. Analisi di Algoritmi: complessità e correttezza; definizione della funzione complessità.
• 10 ottobre. Analisi di complessità: Ordini di grandezza O-grande, Omega-grande, Theta-grande, o-piccolo; proprietà degli ordini di grandezza; strumenti matematici (parte bassa e alta, modulo, sommatorie notevoli); procedimento per provare limiti superiori e inferiori alla complessità
• 15 ottobre. Analisi di complessità: esempi (PrefixAverages quadratico e lineare); esercizio simile a R-4.29 del testo; complessità polinomiale vs complessità esponenziale (esempio: RSA); caveat relativi all'analisi asintotica al caso pessimo.
• 16 ottobre. Tecniche di dimostrazione: esempio, controesempio, per assurdo. Induzione: tecnica genrale, esempi (serie di Gauss, e n-esimo numero di Fibonacci F(n), induzione fallace per provare che F(n)=0). Analisi di correttezza: approccio generale; definizione di invariante; utilizzo di un invariante per provare la correttezza di un ciclo; esempi (arrayMax e arrayFind).
• 17 ottobre. Esercizio: invariante per l'algoritmo che determina il più lungo segmento di 1 consecutivi in una sequenza binaria. Algoritmi ricorsivi: definizione; esempi (LinearSum e ReverseArray); albero della ricorsione; analisi di complessità tramite l'albero della ricorsione; analisi di correttezza; esempi.
• 22 ottobre. Algoritmi ricorsivi: analisi di correttezza; RecurFib; PowerFib. Esercizi: complessità di InsertionSort; algoritmo ricorsivo per la ricerca binaria; algoritmo per la ricerca di una colonna di 0 in una matrice di interi (algoritmo, complessità e invariante).

Materiale di riferimento:

1. Lucidi (finali con errata): Nozioni di Base
2. Esercizi svolti sulle nozioni di base
3. Testo [GTG14]: Paragrafi 1.8.2, 2.1.2, e Capitoli 4 e 5.
   Esercizi consigliati dal libro di testo: R-4.2; R-4.7; R-4.10; R-4.12; R-4.14; R-4.16; R-4.21; R-4.31; R-5.6; C-4.35; C-4.43; C-4.45; C-4.46; C-5.10; C-5.18; C-5.20.

Text Processing

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

Ripasso di Java

• 30 ottobre: Java: programma stand-alone; information hiding; Abstract Data Type (ADT); interfacce; programmazione generica. ADT elementari: Lista (index-based e position-based); Pila; Coda; Java Collection Framework. Esempio: implementazione di InsertionSort con List e ArrayList di Java.

1. Lucidi (finali con errata): Ripasso Java
2. Codice: Esempi di codice Java (cartella zippata)

Alberi

• 31 ottobre: Alberi: applicazioni; definizioni; terminologia; metodi dell'interfaccia Tree; dimostrazione Proposizione 8.3 del testo (esercizio R-8.2); Calcolo della profondità di un nodo (algoritmi ricorsivo e iterativo); calcolo dell'altezza di un nodo e di un albero.
• 5 novembre: Alberi: visite in preorder e postorder (pseudocodici, analisi ed esempi). Algoritmi AllDepths e DiskSum. Esercizi: esercizio simile a R-8.19, e C-8.50.
• 6 novembre: Alberi: fine esercizio C-8.50 e esercizio C-8.27. Alberi binari: definizione; interfaccia. Alberi binari propri: definizione; proprietà (Proposition 8.7 del testo, limitata alla parte sugli alberi binari propri, Proposition 8.8, e Esercizi R-8.7 e R-8.8); visita inorder; Parse Tree di un'espressione.
• 7 novembre: Algoritmo evaluateExpression; algoritmo di ricostruzione della espressione a partire dal Parse Tree di una espressione. Esercizi sugli alberi binari: calcolo della heightsum; conteggio dei nodi strong; algoritmo preorderNext; dimostrazione che in un albero con n nodi e m foglie in cui ogni nodo interno ha almeno 2 figli vale che m >= n-m+1.

Priority Queue

• 12 novembre: Priority Queue: definizione; Interfacce Entry(K,V) e PriorityQueue(K,V); applicazioni reali; implementazione tramite liste (ordinate e non). Albero binario completo: definizione e relazione tra altezza e numero di nodi. Heap: definizione; proprietà realizzazione tramite array (level numbering).
• 13 novembre: Heap: proprietà del level numbering. Implementazione dei metodi della Priority Queue tramite heap su array: pseudocodice e analisi. Esercizio: rimozione di una entry generica da uno heap P.
• 14 novembre: Ripasso per il compitino: Esempio di Compitino 1 (Prima Parte 1 e 2, Seconda Parte 2); Esempio di Compitino 2 (Prima Parte 3, Seconda Parte 2); Esempio di Compitino 3 (Seconda Parte 1 e 2).
• 18 novembre: I Compitino.
• 26 novembre: Correzione del Compitino. Esercizi: rimozione di una entry generica da uno heap P; selezione delle Top-tau entry da una sequenza.
• 27 novembre: Esercizi: stampa delle entry con chiave <=k di uno heap in tempo lineare nel numero di entry stampate. Costruzione di uno heap a partire da un vettore P di n entry: approccio top-down (idea, pseudocodice e complessità); approccio bottom-up (idea, pseudocodice e complessità); confronto tra approccio top-down e approccio bottom-up. Visione compitini.
• 28 novembre: PriorityQueueSort: SelectionSort, InsertionSort, HeapSort come casi particolari. Defimnizione di algoritmo in-place. Implementazione in-place di HeapSort. Caso di studio: simulazione discreta a eventi (ufficio pubblico).
• 3 dicembre: Esercizio sulla identificaizone della m-esima chiave più piccola.

Mappa

• 3 dicembre: Mappa: definizione e applicazioni; interfaccia Map; implementazione tramite lista position-based o array di taglia |U|, con la complessità dei metodi get, put e remove. Esempio: word count. Tabelle Hash: ingredienti principali; nozione di uniform hashing.
• 4 dicembre: Tabelle Hash: 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.
• 5 dicembre: Alberi Binari di Ricerca (ABR): motivazione; 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: Riepilogo implementazione dei metodi della mappa con un Albero Binario di Ricerca. Esercizi: versione iterativa di TreeSearch; conteggio del numero di entry con chiave <=k, con e senza variabile size.
• 11 dicembre: Multi-Way Search Tree: definizione ed esempi; Proposizione 11.2 (ed esercizio C-11.46) del testo; metodo MWTreeSearch(k,v). (2,4)-Tree: definizione; altezza (Proposizione 11.3 del testo); metodi get(k) e put(k,x) (con Split(u))
• 12 dicembre: (2,4)-Tree: esempi di put; metodo remove(k) (con Delete(e,u,alfa)); esempi di remove. MultiMappa: differenze tra MultiMappa e Mappa; specifica dei metodi get(k), put(k,x) e remove(k,v); implementazione tramite Mappa+Liste.
• 17 dicembre: Esercizi nei lucidi: 57 (primo esercizio), 100, 101, 104 (cenni), 105, 107 (secondo esercizio).

Grafi

• 17 dicembre: Definizione di grafo; terminologia; esempi applicativi.
• 18 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.
• 19 dicembre: Algoritmo DFS: pseudocodice; esempio; analisi; visita di tutto il grafo; applicazioni (connettività, spanning tree, s-t reachability, ciclicità).
• 7 gennaio: Esercizio: 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).
• 8 gennaio: Applicazioni della BFS: calcolo di un ciclo. Esercizi: numero di coppie di vertici connesse da cammini; esistenza di un vertice da cui sono raggiungibili almeno n/2 altri vertici, determinazione se un grafo è bipartito, massima separazione tra due vertici (ad es. profili nel grafo di Facebook). 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). QuickSort: strategia generale; pseudocodice in-place (QuickSortInPlace); correttezza di Partition.
• 13 gennaio: QuickSortInPlace: analisi di complessità tramite albero della ricorsione. Algoritmi probabilistici (randomized): distinzione tra la nozione di algoritmo probabilistico e quella di algoritmo deterministico; numero di operazioni eseguite su una data istanza visto come variabile aleatoria. Randomized QuickSort: differenze rispetto a QuickSortInPlace; complessità probabilistica (alta probabilità e media). InsertionSort: algoritmo in place; analisi in funzione della taglia dell'input.
• 15 gennaio: 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). Esercizi: merge di K sequenze ordinate; conteggio dei duplicati in due sequenze ordinate (elementi distinti in ciascuna). BucketSort: algortimo e analisi di complessità. Nozione di ordinamento stabile.
• 16 gennaio: RadixSort: algoritmo; analisi di complessità ; analisi di correttezza. Esempio di applicazione di RadixSort: ordinamento di n chiavi in [0,n^2-1] e generalizzazione all'ordinamento di n chiavi in [0,M-1]. Caso di studio: ordinamento dei cittadini italiani per codice fiscale. Esercizi: conteggio delle chiavi frequenti (Esempio di II Compitino (3)); sorting separato di k sequenze di entry con chiavi in [0,N-1]; conteggio delle inversioni in una sequenza (adattamento di MergeSort).