Analisi Matematica I e II, teoria della probabilità. Capacità di programmazione inl linguaggio C/C++.

Il corso fornisce un'introduzione moderna alla progettazione, analisi ed implementazione di algoritmi sequenziali e paralleli. In particolare, il corso si basa su un approccio pragmatico alla programmazione parallela di algoritmi message-passing attraverso il linguaggio C e la libreria MPI.

Knowledge and understanding.

Gli studenti devono avere un solido background con un ampio spettro di conoscenze di base sugli algoritmi sequenziali e paralleli:

• gli studenti devono possedere gli strumenti cognitivi di base per pensare in modo analitico, creativo, critico e curioso, e possedere le capacità di astrazione e di risoluzione dei problemi necessarie per affrontare sistemi complessi;
• devono avere una solida conoscenza della progettazione e dell'implementazione di algoritmi efficienti sequenziali e paralleli;
• devono possedere gli strumenti per analizzare le risorse utilizzate dagli algoritmi;
• devono possedere un catalogo dei più noti ed efficienti algoritmi sequenziali e paralleli per problemi computazionali di base.
•  

Applying knowledge and understanding.

Al termine del corso lo studente dovrebbe essere in grado di:

• Descrivere e utilizzare le principali tecniche di progettazione di algoritmi sequenziali;
• Progettare, dimostrare la correttezza e analizzare la complessità computazionale di algoritmi sequenziali;
• Comprendere le differenze tra diversi algoritmi che risolvono lo stesso problema e riconoscere quale sia migliore in condizioni diverse;
• Descrivere e utilizzare gli algoritmi sequenziali di base;
• Descrivere e utilizzare le strutture dati di base; conoscere l'esistenza di strutture dati avanzate;
• Comprendere la differenza tra algoritmi sequenziali e paralleli;
• Progettare, implementare e analizzare algoritmi paralleli basati sul message-passing in C/C++ utilizzando la libreria MPI;
• Descrivere e utilizzare algoritmi paralleli di base.

Making judgements. Gli studenti sono guidati ad apprendere criticamente tutto ciò che viene loro spiegato in classe, a confrontare diversi approcci alla soluzione di problemi algoritmici e a identificare e proporre, in modo autonomo, la soluzione più efficienti.

Communication. È fondamentale che lo studente sia in grado di comunicare con un pubblico vario e composito, non culturalmente omogeneo, in modo chiaro, logico ed efficace, utilizzando gli strumenti metodologici acquisiti e le proprie conoscenze scientifiche e, in particolare, il lessico specialistico. Il corso promuove lo sviluppo delle seguenti abilità dello studente: capacità di esporre in termini precisi e formali un modello astratto di problemi concreti, individuandone le caratteristiche salienti e scartando quelle non essenziali; capacità di descrivere e analizzare una soluzione efficace per un dato problema.

Learning skills. Gli studenti devono acquisire la capacità critica di rapportarsi, con originalità e autonomia, alle problematiche tipiche degli algoritmi sequenziali e paralleli e, in generale, alle questioni culturali legate ad altri ambiti simili. Dovranno essere in grado di sviluppare e applicare autonomamente le conoscenze e i metodi appresi in vista di un eventuale proseguimento degli studi a livello superiore (dottorato) o nella più ampia prospettiva di auto-miglioramento culturale e professionale dell'apprendimento permanente. Pertanto, gli studenti devono essere in grado di passare a forme espositive diverse dai testi di partenza per memorizzare, riassumere per sé e per gli altri e diffondere le conoscenze scientifiche.

Il corso si propone di mettere gli studenti in grado di astrarre modelli e problemi algoritmici formali da problemi computazionali concreti e di progettare soluzioni algoritmiche efficienti per questi ultimi. A tal fine si utilizzerà il seguente metodo di insegnamento. Ogni problema computazionale sarà introdotto motivandolo con esempi concreti. La presentazione di ogni argomento sarà divisa in quattro parti: 1. Descrizione del problema computazionale concreto. 2. Modellazione del problema reale mediante un problema astratto. 3. Risoluzione del problema astratto attraverso un algoritmo ottenuto con l'applicazione delle tecniche generali di progettazione di algoritmi introdotte nel corso. 4. Analisi delle risorse utilizzate dall'algoritmo. Il corso consiste in lezioni frontali ed esercitazioni in aula. Ci saranno lezioni teoriche finalizzate all'apprendimento delle tecniche di base per la progettazione e l'analisi degli algoritmi, e una parte delle lezioni dedicata alle esercitazioni in cui si illustrerà, con dovizia di esempi, come le conoscenze teoriche acquisite possano essere utilizzate per risolvere problemi algoritmici di interesse pratico e implementare algoritmi paralleli in linguaggio C/C++ attraverso la libreria MPI.

L'esame consiste in una prova scritta e nell'implementazione di un prototipo di software parallelo. La prova scritta (2 ore, 21 punti su 30) verte su argomenti teorici relativi alla progettazione e all'analisi di algoritmi sequenziali e paralleli, al fine di verificare la conoscenza e la comprensione della materia da parte dello studente. Per superare la prova scritta, gli studenti dovranno ottenere almeno 9 punti su 21.  Il progetto di software parallelo (9 punti su 30) ha lo scopo di verificare la pratica della programmazione parallela e la capacità dello studente di implementare algoritmi paralleli teorici o di parallelizzare un algoritmo sequenziale. Per superare la prova di programmazione parallela, gli studenti devono ottenere almeno 4 punti su 9. Sia la prova scritta che l'implementazione del prototipo di software parallelo sono obbligatori. Gli studenti devono superare sia la prova scritta sia la prova di programmazione parallela; l'esame è superato solo se la somma dei punti ottenuti nella prova scritta e in quella di programmazione parallela è maggiore o uguale a 18 punti.

Il problema da risolvere in parallelo (o un algoritmo sequenziale da implementare in parallelo) viene assegnato su richiesta dello studente. Il progetto di software parallelo assegnato può essere discusso solo se la prova scritta è stata superata con successo; inoltre, il progetto di software parallelo deve essere obbligatoriamente discusso nella stessa prova in cui è stata superata la prova scritta.

La relazione relativa al progetto assegnato deve essere strutturata come segue.

1. Introduzione. Lo studente deve fornire una descrizione accurata del progetto assegnato, comprensiva dell’analisi dell’algoritmo sequenziale che risolve il problema affrontato nel progetto. Qualora lo studente lo ritenga importante ai fini della comprensione, possono essere presenti pseudo-codice, esempi, grafici, figure, istanze applicative etc; 

2. Design parallelo. Si tratta di uno studio preliminare volto ad evidenziare le opportunità per il parallelismo insite nel problema e/o nell'algoritmo sequenziale di partenza. Partendo dallo pseudo-codice occorre quindi determinare le funzionalità, le parti di codice e/o le strutture dati più opportune che possono essere prese in considerazione per la parallelizzazione. In questa fase devono essere considerati e discussi design alternativi, relativi a diverse strategie di parallelizzazione, motivando opportunamente perché alcune operazioni si prestano ad una parallelizzazione efficace ed altre no. Inoltre, devono essere riportati i risultati attesi, inclusa l’analisi della complessità parallela nel caso peggiore. È richiesta massima chiarezza espositiva in merito alla strategia di parallelizzazione, pertanto le strutture dati utilizzate devono essere descritte integralmente, motivando le scelte adottate per minimizzare il peso  delle comunicazioni e della sincronizzazione. La valutazione analitica teorica della scalabilità della versione parallela è obbligatoria, e deve essere eseguita sia utilizzando la isoefficienza che la funzione di scalabilità. 

3. Implementazione. Il design parallelo adottato deve essere implementato utilizzando il linguaggio di programmazione C o, eventualmente, C++ (in modo da usare le strutture dati presenti nella STL del C++). Il codice deve essere necessariamente commentato in modo adeguato. Nel caso in cui lo studente verifichi l’esistenza di strategie di parallelizzazione multiple per lo stesso problema assegnato, è possibile fornire una implementazione per ciascuna strategia, discutendo vantaggi e svantaggi di ogni strategia. Si noti che il codice parallelo non deve essere riportato integralmente nel testo della relazione, in quanto il codice del progetto - sorgenti e Makefile per il build (in alternativa è possibile usare CMake) - deve in ogni caso essere consegnato a parte. Tuttavia, la relazione può includere alcuni snippet di codice relativi alla parti più critiche ed interessanti. 

4. Debug e test. Si raccomanda di effettuare un debug e test del codice parallelo che consenta di verificare, ragionevolmente, l’assenza di bugs e la correttezza dell’algoritmo parallelo in relazione all’output prodotto. Si invita lo studente a progettare e verificare gli unit tests ritenuti idonei a valutare la bontà del codice. Lo studente è esplicitamente avvisato che l’implementazione di una strategia di parallelizzazione non corretta e/o la presenza di bugs che mandano in crash l'applicazione parallela a runtime comportano il non superamento dell'esame, mentre la presenza di bugs che inficiano la correttezza dell'algoritmo comporta una penalizzazione relativa al punteggio che sarà attribuito. 

5. Analisi delle prestazioni e della scalabilità. Lo studente deve analizzare le prestazioni dell’implementazione sviluppata in termini di tempo di esecuzione, occupazione di memoria (se necessario), speedup ed efficienza. Deve essere valutata sia la strong scalability (Amdahl) che la weak scalability (Gustafson) ove possibile. 

6. Sintesi. La relazione deve essere quanto più possibile sintetica, ma senza che ciò vada a discapito della chiarezza espositiva. 

7. Valutazione del progetto. Il progetto sarà valutato con un punteggio relativo ad una scala che va da 1 a 9 punti. Il voto sarà definito solo al termine della discussione del progetto. La complessità del problema assegnato sarà presa in considerazione per la valutazione; gli studenti che si occupano di problemi più semplici devono quindi aspettarsi una minore indulgenza nella valutazione rispetto agli studenti che si occupano di problemi più difficili. 

La valutazione terrà inoltre conto di: 

- Chiarezza ed efficacia della presentazione; 

- Profondità, correttezza ed originalità dell’analisi teorica; 

- Capacità tecniche e documentazione dell’implementazione; 

- Numero e qualità delle strategie multiple parallele, ove presenti; 

- Pensiero critico nella valutazione e nell’analisi delle prestazioni; 

• Significatività dei risultati: dato che la programmazione parallela si occupa principalmente di prestazioni, un buon progetto deve anche fornire un significativo speedup.

8. Plagio. Lo studente è avvisato esplicitamente che il plagio è gravissimo, ed è considerato molto seriamente. L’uso di fonti esterne di qualsiasi genere (internet, libri, dispense, lavori pregressi di altri studenti etc) è consentito solo per contributi marginali nel progetto (ad esempio, per la descrizione iniziale del progetto assegnato), ed ogni singola occorrenza deve essere esplicitamente citata e riportata nella relazione. La violazione di questo codice di comportamento non sarà in alcun modo tollerata, e comporta l’immediato annullamento dell’esame ed il deferimento dello studente alla commissione disciplinare di ateneo, con avvio del relativo procedimento disciplinare secondo quanto riportato del Titolo V (PROCEDIMENTI DISCIPLINARI E SANZIONI) del Regolamento di Ateneo per gli studenti (D.R. 672 del 5/12/2017, entrato in vigore in data 8/12/2017).

Ricevimento Studenti

Su appuntamento; contattare il docente via e-mail o al termine degli incontri di classe.

Parallel Algorithms

Introduction. Parallel Architectures. Parallel algorithm design. Message-Passing Programming. Sieve of Erathostenes. Floyd all-pairs shortest path algorithm. Performance analysis. Matrix-vector multiplication. Document classification. Matrix multiplication. Linear Systems. Finite Difference Methods. Sorting. 

Parallel Programming

Message-Passing programming using MPI.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer. Divide and conquer. Recurrences. Randomized algorithms. Transform and conquer.  Dynamic programming. Greedy algorithms. Single Source Shortest Paths. Dijkstra algorithm. Breadth-First Search. Bellman-Ford Algorithm. Complexity and computability. NP-Completeness. The transition from sequential to parallel computing. Parallel complexity.

Introduction to Algorithms. Fourth edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP (International Edition). Michael J. Quinn. McGraw-Hill

Analisi Matematica I e II. Teoria della probabilità. Algebra lineare. Capacità di programmazione in linguaggio C/C++.

Il corso fornisce un'introduzione moderna al data mining ed al machine learning, che comprendono tecniche, algoritmi e metodologie per scoprire strutture, schemi e relazioni in insiemi di dati (tipicamente di grandi dimensioni) e fare previsioni. Le applicazioni del data mining e del machine learning sono già presenti intorno a noi e, quando sono fatte bene, a volte passano addirittura inosservate. Per esempio, come funziona la ricerca web di Google? Come fa Netflix a consigliare i film ai suoi utenti? I principi del data mining e del machine learning forniscono risposte a queste e altre domande. Il data mining ed il machine learning intersecano i campi dell'informatica, dell'apprendimento statistico e delle basi di dati. Il corso mira a fornire agli studenti le conoscenze necessarie per esplorare, analizzare e sfruttare i dati disponibili al fine di trasformarli in informazioni preziose e utilizzabili per un'azienda, ad esempio per facilitare il processo decisionale.

Knowledge and understanding. Il corso descrive metodi e modelli per l'analisi di grandi quantità di dati. Gli studenti devono avere un solido background con un ampio spettro di conoscenze di base relative al data mining:

• gli studenti devono possedere gli strumenti cognitivi di base per pensare in modo analitico, creativo, critico e curioso, e possedere le capacità di astrazione e di risoluzione dei problemi necessarie per affrontare sistemi complessi;
• devono avere una solida conoscenza dei modelli e delle metodologie di data mining;
• devono essere in grado di lavorare su grandi raccolte di dati, anche eterogenei e prodotti ad alta velocità, al fine di integrarli - in particolare sapendo gestirne l'origine e la qualità - e di effettuare analisi tematiche approfondite, attingendo a queste conoscenze per migliorare il processo decisionale.

Applying knowledge and understanding. Al termine del corso lo studente dovrà essere in grado di:

• descrivere e utilizzare le principali tecniche di data mining;
• comprendere le differenze tra diversi algoritmi che risolvono lo stesso problema e riconoscere quale sia il migliore in diverse condizioni;
• affrontare nuovi problemi di data mining selezionando i metodi appropriati e giustificando le proprie scelte;
• affrontare nuovi problemi di data mining progettando algoritmi adeguati e valutando i risultati;
• spiegare i risultati sperimentali a persone estranee al machine learning o all'informatica.

Making judgements. Lo studente deve avere la capacità di elaborare dati complessi e/o frammentari e deve giungere a idee e giudizi originali e autonomi, nonché a scelte coerenti nel contesto del proprio lavoro, particolarmente delicate nella professione del data scientist. Il corso promuove lo sviluppo dell'autonomia di giudizio nella scelta appropriata di tecniche/modelli per l'elaborazione dei dati e la capacità critica di interpretare la bontà dei risultati dei modelli/metodi applicati ai dataset in esame.

Communication. È fondamentale che gli studenti siano in grado di comunicare con un pubblico vario e composito, non culturalmente omogeneo, in modo chiaro, logico ed efficace, utilizzando gli strumenti metodologici acquisiti e le loro conoscenze scientifiche e, in particolare, il lessico specialistico. Gli studenti devono essere in grado di organizzare materiale divulgativo e di studio efficacemente, attraverso i più comuni strumenti di presentazione anche informatici, per comunicare i risultati dei processi di analisi dei dati, ad esempio utilizzando strumenti di visualizzazione e reportistica rivolti a diversi tipi di pubblico.

Learning skills. Gli studenti devono acquisire la capacità critica di rapportarsi, con originalità e autonomia, alle problematiche tipiche del data mining e, in generale, alle questioni culturali legate ad altri ambiti simili. Dovranno essere in grado di sviluppare e applicare autonomamente le conoscenze e i metodi appresi in vista di un eventuale proseguimento degli studi a livello superiore (dottorato) o nella più ampia prospettiva di auto-miglioramento culturale e professionale dell'apprendimento permanente. Pertanto, gli studenti devono essere in grado di passare a forme espositive diverse dai testi di partenza per memorizzare, riassumere per sé e per gli altri e diffondere le conoscenze scientifiche.

Il corso si propone di fornire agli studenti strumenti avanzati per l'analisi dei dati, attraverso i quali estrapolare informazioni rilevanti da grandi insiemi di dati e guidare i relativi processi decisionali. Il corso si articola in lezioni frontali, con l'ausilio di slide messe a disposizione degli studenti tramite la piattaforma e-learning di UniSalento, ed esercitazioni in aula. Le lezioni frontali mirano a migliorare la conoscenza e la comprensione degli studenti attraverso la presentazione di teorie, modelli e metodi; gli studenti sono invitati a partecipare alla lezione con autonomia di giudizio, ponendo domande e presentando esempi. Le esercitazioni sono finalizzate alla comprensione degli algoritmi e dei modelli presentati.

Progetto software ed esame orale. Durante l'esame viene chiesto allo studente di illustrare argomenti teorici per verificare la sua conoscenza e comprensione degli argomenti selezionati. Lo studente deve dimostrare un'adeguata conoscenza e comprensione degli argomenti presentati o indicati, applicando in modo pertinente le teorie e i modelli concettuali oggetto del programma di studio. L'esame orale è valutato su una scala da 18 a 30 punti. Il progetto software viene assegnato su richiesta dello studente e deve essere obbligatoriamente discusso nella stessa prova in cui si svolge l'esame orale. Il progetto software è valutato su una scala da 18 a 30 punti. Il voto finale è dato dalla media dei voti ottenuti, e l'esame è superato se il voto conseguito è almeno pari a 18.

La relazione relativa al progetto assegnato deve essere strutturata come segue.

1. Introduzione. Lo studente deve fornire una descrizione accurata del progetto assegnato, comprensiva dell’analisi dell’algoritmo sequenziale che risolve il problema affrontato nel progetto. Qualora lo studente lo ritenga importante ai fini della comprensione, possono essere presenti pseudo-codice, esempi, grafici, figure, istanze applicative etc; 

2. Implementazione. Il software deve essere implementato utilizzando il linguaggio di programmazione C o, eventualmente, C++ (in modo da usare le strutture dati presenti nella STL del C++). Il codice deve essere necessariamente commentato in modo adeguato. Nel caso in cui lo studente verifichi l’esistenza di strategie multiple per lo stesso problema assegnato, è possibile fornire una implementazione per ciascuna strategia, discutendo vantaggi e svantaggi di ogni strategia. Si noti che il codice non deve essere riportato integralmente nel testo della relazione, in quanto il codice del progetto - sorgenti e Makefile per il build (in alternativa è possibile usare CMake) - deve in ogni caso essere consegnato a parte. Tuttavia, la relazione può includere alcuni snippet di codice relativi alla parti più critiche ed interessanti. 

3. Debug e test. Si raccomanda di effettuare un debug e test del codice che consenta di verificare, ragionevolmente, l’assenza di bugs e la correttezza dell’algoritmo in relazione all’output prodotto. Si invita lo studente a progettare e verificare gli unit tests ritenuti idonei a valutare la bontà del codice. Lo studente è esplicitamente avvisato che l’implementazione di una strategia risolutiva non corretta e/o la presenza di bugs che mandano in crash l'applicazione a runtime comportano il non superamento dell'esame, mentre la presenza di bugs che inficiano la correttezza dell'algoritmo comporta una penalizzazione relativa al punteggio che sarà attribuito. 

4. Analisi delle prestazioni e della scalabilità. Lo studente deve analizzare le prestazioni dell’implementazione sviluppata in termini di tempo di esecuzione ed occupazione di memoria se necessario. Deve essere valutata la scalabilità dell’algoritmo al variare della problem size. 

5. Sintesi. La relazione deve essere quanto più possibile sintetica, ma senza che ciò vada a discapito della chiarezza espositiva. 

6. Valutazione del progetto. Il progetto sarà valutato con un punteggio relativo ad una scala che va da 1 a 30 punti. Il voto sarà definito solo al termine della discussione del progetto. La complessità del problema assegnato sarà presa in considerazione per la valutazione; gli studenti che si occupano di problemi più semplici devono quindi aspettarsi una minore indulgenza nella valutazione rispetto agli studenti che si occupano di problemi più difficili. 

La valutazione terrà inoltre conto di: 

- Chiarezza ed efficacia della presentazione; 

- Capacità tecniche e documentazione dell’implementazione; 

- Pensiero critico nella valutazione e nell’analisi delle prestazioni; 

• Significatività dei risultati: dato che le prestazioni sono lo scopo principale, un buon progetto deve anche fornire prestazioni significative.

7. Plagio. Lo studente è avvisato esplicitamente che il plagio è gravissimo, ed è considerato molto seriamente. L’uso di fonti esterne di qualsiasi genere (internet, libri, dispense, lavori pregressi di altri studenti etc) è consentito solo per contributi marginali nel progetto (ad esempio, per la descrizione iniziale del progetto assegnato), ed ogni singola occorrenza deve essere esplicitamente citata e riportata nella relazione. La violazione di questo codice di comportamento non sarà in alcun modo tollerata, e comporta l’immediato annullamento dell’esame ed il deferimento dello studente alla commissione disciplinare di ateneo, con avvio del relativo procedimento disciplinare secondo quanto riportato del Titolo V (PROCEDIMENTI DISCIPLINARI E SANZIONI) del Regolamento di Ateneo per gli studenti (D.R. 672 del 5/12/2017, entrato in vigore in data 8/12/2017).

Ricevimento studenti

Su appuntamento; contattare il docente via e-mail o al termine degli incontri di classe.

Introduction to the course.

Introduction to the Map-Reduce parallel programming model. Open-source Hadoop implementation. Pros and cons of Hadoop and Map-Reduce. Distributed File System. Chunk servers, Master node. Map Function. Sort and Shuffle. Reduce Function. Map Tasks. Reduce Tasks. Word counting. Handling failures. Number of Map and Reduce jobs. Granularity of tasks and pipelining. Strugglers tasks: mitigating the problem by spawning backup tasks. Combiners. Partition (hash) function. Additional examples of Map-Reduce: natural join, two-pass matrix multiply, single pass matrix multiply. Cost measures for Map-Reduce algorithms.

Frequent Pattern Mining. Discovery of association rules. Market-basket model. Examples of possible applications. Frequent itemsets. Support of an itemset. Association rules. Confidence and Interest. Association rules with highly positive or negative interest. Mining association rules. Maximal and closed frequent itemsets. Lattice of the itemsets. Naive approach to counting frequent pairs. A-priori. Monotonicity. PCY. PCY refinements: multistage and multihash. Frequent itemsets in 2 passes: random sampling and choice of the threshold, SON, monotonicity, parallel SON parallelo with Map-Reduce in 2 passes, Toivonen and the negative border. ECLAT. DECLAT. FPGrowth.  Sequence mining. Frequent sequences. Mining frequent sequences. GSP. SPADE. PREFIXSPAN. 

Streams. Uniform, 2-universal and pairwise independent hash function. Streaming: turnstile, strict turnstile and cash register models. Frequency estimation. Sketches. Count-Sketch. Count-Min. Comparing Count-Sketch and Count-Min. Frequent items. Phi-frequent items. The majority problem. Boyer-Moore. Misra-Gries. Frequent. Space Saving. Space Saving properties. Comparing Frequent and Space Saving. Sampling from a Data Stream: Sampling a fixed proportion. Sampling a fixed-size sample: varying the sample size. Reservoir Sampling. Queries over a sliding windows: counting the number of bits equal to 1 with DGIM. Filtering data streams: Bloom FIlters. Counting distinct elements: Flajolet-Martin. Estimating moments with AMS.

Scene completion problem. Near neighbors in high dimensionality spaces. Document similarity. Pairs of candidate documents. Near neighbor search. Jaccard similarity and distance. Shingling: how to convert documents, emails etc in sets. k-shingles. Compression through hashing of k-shingles. Min-Hashing: converting big sets in short signatures preserving the similarity. Similarity and Jaccard distance for boolean vectors. Boolean matrices. Min-hash signatures. Implementation. Locality-Sensitive Hashing: determining pairs of candidate documents. Matrix partitioning in b bands of r rows: analysis of accuracy with regard to  false positives and false negatives.

Link analysis. PageRank. Dead ends. Spider traps. Flow formulation. Matrix formulation. Random walk interpretation. Stationary distribution of a Discrete-Time Markov Chain. Perron-Frobenius Theorem. Google matrix and teleportation. Sparse matrix encoding. Block update algorithm. Topic-specific PageRank. Matrix formulation. Topic vector. Web Spam. Term spam. Spam farms. PageRank value obtained through a Spam Farm. TrustRank. Trust propagation. Spam Mass estimation.

Recommender systems. Recommendations. The long tail phenomenon. Content-based systems. Utility function and matrix. Ratings. Extrapolation of ratings (utilities). Item profiles. User profiles. Collaborative filtering. k-NN. Similarity metrics. User-user and item-item collaborative filtering. Evaluation of systems. Error metrics. RMSE, precision, rank correlation. Complexity of collaborative filtering. The Netflix challenge. Bellkor recommender system. Modeling local and global effects. Learning the optimal weights: optimization problem and gradient descent. Latent factor models. SVD decomposition. Learning the P and Q matrices. Preventing overfitting: regularization. Stochastic Gradient Descent. Biases and interactions. Temporal biases and factors.

Artificial Intelligence. Different definitions over time: thinking like a human, acting like humans and the Turing test, thinking rationally, acting rationally. Rational agents, decisions and behaviour. Game playing: chess, go, etc. The human intelligence. Human versus artificial intelligence. Benefits of AI. Ai, machine learning and deep learning. AI applications and use-cases. Human learning process. Features, instances, labels, classes, classification function. Training set, validation and test set. Supervised learning: regression, binary and multiclass classification. Unsupervised learning. Semi-supervised and weakly-supervised learning. Reinforcement learning: agent, environment and its state that changes depending on the agent's actions, reward and penalty. Loss functions. Zero-one and squared loss functions. Bias and variance. Deep Learning. Machine Learning vs Deep Learning. Limitations of Deep Learning. Artificial versus biological neural networks. AI Myths.

The clustering problem. Curse of dimensionality. Clustering in euclidean and non euclidean spaces. Distances. Hierarchical clustering: agglomerative and divisive algorithms. Clustering by point assignment. Centroid and clustroid. K-means and K-means++. Choosing k: elbow criterion. BFR. Discard, Compression and Retained sets. Summarizing points. Mahalanobis distance. CURE. Representative points and their choice. Input space and feature space. Kernel methods. Kernel matrix. Linear kernel. Kernel trick. Kernel operations in feature space. Represenative clustering: K-means and Kernel K-means. Expectation-Maximization clustering. Hierarchical clustering. Density-based clustering. DBSCAN. Clustering validation: external, internal and relative measures.

Machine learning. Supervised and unsupervised approaches. Numerical and categorical attributes. Categorical attributes: nominal and ordinal attributes. Probabilistic classifiers. Parametric approach: Bayes and naive Bayes classifiers. Data centering. Non parametric approach (density based): K-nearest neighbors classifier. Decision Trees. Hyperplans. Split points. Data partion and purity. Split Point Evaluation Measures: entropy, split entropy, information gain, Gini index, CART. Evaluation of numerical and categorical split points. Support Vector machines. Hyperplanes. Support Vectors and Margins. Linear and Separable Case. Soft Margin SVM: Linear and Nonseparable Case. Kernel SVM: Nonlinear Case. SVM Training Algorithms. Multiclass SVM. Assessing the performances of a classifier. Evaluation metrics. ROC curve and AUC. K-fold cross-validation. Bootstrapping. Confidence intervals. Paired t-Test. Bias and variance decomposition. Ensemble classifiers. Bagging. Random Forest. Boosting. Stacking.

Mining of Massive Datasets, 3rd edition

J. Leskovec, A. Rajaraman and J. Ullman

Freely available online: http://www.mmds.org

Data Mining and Analysis, 2nd edition

M. J. Zaki and W. Meira

Freely available online: http://dataminingbook.info

Non vi è alcuna propedeuticità per il corso.

In sintesi il laboratorio affronta i seguenti temi: introduzione alle architetture dei dati, introduzione all'analisi dei dati tramite linguaggio SQL, struttura dei sistemi di calcolo, concetto di algoritmo ed elementi della programmazione strutturata, introduzione al linguaggio di programmazione Python.

Il corpus principale del laboratorio intende dunque fornire le basi pratiche per la modellazione e l'analisi dei dati e, parallelamente, per l'elaborazione dei dati sviluppando semplici programmi Python. Ogni concetto esposto è sperimentato in modo pratico insieme agli studenti utilizzando il personal computer e strumenti di sviluppo moderni e ampiamente diffusi nel mondo industriale.

Conoscenze e comprensione. Al termine del corso gli studenti: (a) conosceranno i principi della programmazione strutturata, in relazione alle caratteristiche del software; (b) conosceranno gli aspetti generali del linguaggio Python cioè programmazione con i tipi di dati fondamentali, le strutture di controllo, le funzioni, le liste, i file, gli insiemi e i dizionari; (c) comprenderanno le tecniche di codifica in Python di algoritmi; (d) comprenderanno come utilizzare i principali ambienti di sviluppo Python anche in relazione delle singole necessità rappresentate nei requisiti del software e nella strutturazione dei dati.

Inoltre, al termine del corso gli studenti conosceranno il linguaggio SQL, necesssario per interagire con una base di dati. In particolare: (a) gli statements (DDL, Data Definition Language) necessari per specificare lo schema concettuale ed interno di un DBMS (Data Base Management System) ed il mapping tra i due; (b) gli statements (DML, Data Manipulation Language) necessari per manipolare una base di dati. Le operazioni tipicamente supportate includono il recupero, l’inserimento, la cancellazione e la modifica dei dati.

Capacità di applicare conoscenze e comprensione. Gli studenti saranno in grado di applicare le conoscenze acquisite in diversi ambiti applicativi e, in generale, per la codifica al computer in linguaggio Python di logica di business. Inoltre, gli studenti saranno in grado di creare ed interrogare una base di dati.

Autonomia di giudizio. Il corso favorisce l'autonomia di giudizio degli studenti attraverso l'analisi critica di problemi di modellazione del software da requisiti funzionali e non funzionali, per i quali trovare le soluzioni adeguate a risolverli in linguaggio Python. Diverse soluzioni proposte interattivamente dagli studenti saranno poste a confronto e valutate criticamente dagli studenti stessi. Inoltre, gli studenti devono possedere la capacità di problem solving e devono pervenire a idee e giudizi originali e autonomi, a scelte coerenti nell’ambito del loro lavoro, particolarmente delicate nell’ambito della implementazione di una base di dati. Il corso promuove lo sviluppo dell’autonomia di giudizio nella scelta appropriata della soluzione migliore relativa a semplici problemi legati all’interazione con una base di dati e la capacità critica di interpretare la bontà dei risultati ottenuti.

Abilità comunicative. Gli studenti apprenderanno come comunicare adeguatamente e con il corretto livello di formalismo le scelte di design adottate e le strategie di implementazione scelte. Il metodo di insegnamento interattivo e teorico/pratico favorirà momenti di confronto in cui mettere in pratica tali abilità comunicative. È fondamentale che gli studenti siano in grado di comunicare con un pubblico vario e composito, non omogeneo culturalmente, in modo chiaro, logico ed efficace, utilizzando gli strumenti metodologici acquisiti e le loro conoscenze scientifiche e, in particolar modo, il lessico di specialità. Il corso favorisce lo sviluppo delle abilità inerenti le capacità di esporre in termini precisi e formali snippets di codice sorgente in linguaggio Python e queries SQL.

Capacità di apprendimento. La materia in costante evoluzione (sia le tecniche di sviluppo del software, sia i linguaggi che le implementano) richiederà agli studenti la capacità di aggiornarsi e di ricercare materiale on-line, valutandone anche la qualità. Il metodo didattico favorirà l’approfondimento autonomo da parte degli studenti, incuriosendoli su tecniche di sviluppo evolute (vedi i design pattern). Gli studenti fevono inoltre essere in grado di riusare le conoscenze legate alle basi di dati indipendentemente dallo specifico DBMS utilizzato.

Lezioni frontali in laboratorio con ampio spazio a esercitazioni pratiche svolte con l’uso del personal computer, creazione individuale di semplici basi di dati, elaborazione di script SQL e di programmi Python.

L'esame prevede una prova orale per la verifica dell'apprendimento dei concetti teorici (verifica delle conoscenze) e della capacità di applicazione dei medesimi, in particolare per la codifica autonoma di basi di dati, di script SQL e di semplici programmi Python (verifica delle competenze). Durante l’esame lo studente dovrà usare il personal computer, configurato con gli ambienti di sviluppo illustrati e utilizzati in laboratorio.

Si veda www.disteba.unisalento.it.

www.unisalento.it/people/luca.mainetti

www.unisalento.it/people/massimo.cafaro

Ricevimento Studenti

Su appuntamento; contattare il docente via e-mail o al termine degli incontri di classe.

Presentazione dettagliata del modulo Python (1 ora). Struttura dei sistemi di calcolo (2 ore). Il concetto di algoritmo (1 ora). Introduzione al linguaggio Python (2 ore). Programmare con numeri e stringhe (2 ore). Decisioni (2 ore). Cicli (2 ore). Funzioni (2 ore). Liste (2 ore). Eccezioni e file (2 ore). Insiemi e dizionari (2 ore).

Il linguaggio SQL. Definizione dei dati e tipi di dato. I concetti di schema e catalogo. Statement CREATE SCHEMA. Statement CREATE TABLE. Tipi di dato di un attributo. Statement CREATE DOMAIN. Specifica di vincoli in SQL. Vincoli sugli attributi e valori di default per gli attributi. PRIMARY Key, FOREIGN KEY, integrità referenziale. Clausola UNIQUE, clausola CHECK per vincoli su tuple. Query SELECT. Aliases. Eliminare tuple duplicate con DISTINCT. Tabelle come insiemi: operazioni UNION, EXCEPT, INTERSECT. Tabelle come multi-insiemi: UNION ALL, EXCEPT ALL, INTERSECT ALL. Pattern matching per sottostringhe ed operatori aritmetici. Ordinare i risultati di una query: ORDER BY. (3 ore)

Statement INSERT. Statement DELETE. Statement UPDATE. Valori NULL. Logica basata sui tre valori TRUE, FALSE ed UNKNOWN. Queries annidate. Queries annidate correlate. Funzioni EXISTS e UNIQUE. Insiemi espliciti e ridenominazione di attributi in SQL. (3 ore).

JOIN, NATURAL JOIN, OUTER JOIN (left, right, full). Funzioni di aggregazione: COUNT, SUM, MAX, MIN, AVG. Clausola GROUP BY. Clausola HAVING. Clausola WITH. Costrutto CASE. Queries ricorsive. Concetto di vista in SQL. Statement CREATE VIEW. Statement DROP VIEW. Autorizzazione: statements GRANT e REVOKE. Statement DROP. Statement ALTER. (3 ore)

Il DBMS SQLite. (3 ore)

Accesso ed interazione con una base di dati SQLite in Python. (8 ore)

- Cay Horstmann, Rance D. Necaise, “Concetti di Informatica e Fondamenti di Python”, Seconda Edizione, Apogeo Education, Maggioli Editore, 2019.

- Ramez Elmasri, Shamkant B. Navathe, “Fundamentals of Database Systems”, 7th Edition, Pearson, 2015.

- Materiale didattico fornito dal docente tramite il sito elearning.unisalento.it.

Calculus. Probability theory. Linear Algebra. Programming skills.

The course provides a modern introduction to data mining, which spans techniques, algorithms and methodologies for discovering structure, patterns and relationships in data sets (typically, large ones) and making predictions. Applications of data mining are already happening all around us, and, when they are done well, sometimes they even go unnoticed. For instance, how does the Google web search work? How does Netflix recommend movies to its users? The principles of data mining provide answers to these and others questions. Data mining overlaps the fields of computer science, statistical machine learning and data bases. The course aims at providing the students with the knowldedge required to explore, analyze and leverage available data in order to turn the data into valuable and actionable information for a company, for instance, in order to facilitate a decision-making process.

Knowledge and understanding. The course describes methods and models for the analysis of large amounts of data. Students must have a solid background with a broad spectrum of basic knowledge related to data mining:

• the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;
• they must have solid knowledge of data mining models and methodologies;
• they must be able to work on large data collections, including heterogeneous and produced at high speed data, in order to integrate them - in particular by knowing how to manage their origin and quality - and to carry out in-depth thematic analyses, drawing on this knowledge to improve the decision-making process.

Applying knowledge and understanding. After the course the student should be able to:

• describe and use the main data mining techniques;
• understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;
• tackle new data mining problems by selecting the appropriate methods and justifying his/her choices;
• tackle new data mining problems by designing suitable algorithms and evaluating the results;
• explain experimental results to people outside of statistical machine learning or computer science.

Making judgements. Students must have the ability to process complex and/or fragmentary data and must arrive at original and autonomous ideas and judgments, and consistent choices in the context of their work, which are particularly delicate in the profession of data scientist. The course promotes the development of independent judgment in the appropriate choice of technique/model for data processing and the critical ability to interpret the goodness of the results of the models/methods applied to the datasets under examination.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. Students should be able to organize effective dissemination and study material through the most common presentation tools, including computer-based ones, to communicate the results of data analysis processes, for example by using visualization and reporting tools aimed at different types of audiences.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to provide students with advanced tools for data analysis, through which to extrapolate relevant information from large datasets and guide the related decision-making processes. The course consists of frontal lessons using slides made available to students via the UniSalento e-learning platform, and classroom exercises. The frontal lessons are aimed at improving students' knowledge and understanding through the presentation of theories, models and methods; students are invited to participate in the lesson with autonomy of judgement, by asking questions and presenting examples. The exercises are aimed at understanding the algorithms and models presented.

Software project and oral exam. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student must demonstrate adequate knowledge and understanding of the issues presented or indicated, applying in a relevant manner the theories and conceptual models covered by the study programme. The oral exam is evaluated on a scale from 18 to 30 points. The software project is assigned upon request to the student, and must be mandatorily discussed into the same trial in which the oral test is performed. The software project is evaluated on a scale from 18 to 30 points. The final grade is given by the average of the grades obtained, and the exam is passed if the grade achieved is at least 18.

The report on the assigned project must be structured as follows.

1. Introduction. The student must provide an accurate description of the assigned project, including an analysis of the sequential algorithm that solves the problem addressed in the project. If the student deems it important for understanding, then pseudo-code, examples, graphs, figures, application instances etc. may be included; 

2. Implementation. The software must be implemented using the C or, possibly, C++ programming language (so as to use the data structures present in the C++ STL). The code must necessarily be appropriately commented. In the event that the student verifies the existence of multiple solution strategies for the same assigned problem, an implementation can be provided for each strategy, discussing the advantages and disadvantages of each strategy. Note that the code does not have to be given in full in the text of the report, as the project code - source and Makefile for the build (alternatively CMake can be used) - must in any case be delivered separately. However, the report may include some code snippets relating to the most critical and interesting parts. 

3. Debugging and testing. It is recommended to debug and test the code in order to reasonably verify the absence of bugs and the correctness of the algorithm in relation to the output produced. The student is urged to design and test unit tests deemed suitable for assessing the goodness of the code. The student is explicitly warned that the implementation of an incorrect solving strategy and/or the presence of bugs that crash the application at runtime will result in failing the exam, while the presence of bugs that affect the correctness of the algorithm will result in a penalty relative to the mark that will be awarded.

4. Performance and scalability analysis. The student must analyse the performance of the implementation developed in terms of execution time and memory occupation if necessary. The scalability of the algorithm as the problem size changes must be assessed. 

5. Synthesis. The report must be as concise as possible, but without detriment to clarity of presentation. 

6. Project evaluation. The project will be assessed on a scale of 1 to 30 points. The grade will only be determined at the end of the project discussion. The complexity of the problem assigned will be taken into account in the assessment; students dealing with simpler problems should therefore expect less leniency in the assessment than students dealing with more difficult problems. 

Assessment will also take into account: 

- Clarity and effectiveness of presentation; 

- Technical skills and documentation of implementation; 

- Critical thinking in evaluation and performance analysis; 

- Meaningfulness of results: since performance is the main purpose, a good project must also deliver meaningful performance.

7. Plagiarism. The student is explicitly warned that plagiarism is very serious, and is taken very seriously. The use of external sources of any kind (internet, books, handouts, previous work by other students etc.) is only allowed for marginal contributions in the project (e.g. for the initial description of the assigned project), and each individual occurrence must be explicitly cited and reported in the report. Violation of this code of conduct will not be tolerated in any way, and will result in the immediate cancellation of the examination and the referral of the student to the University Disciplinary Committee, with the commencement of the relevant disciplinary proceedings in accordance with the provisions of Title V (DISCIPLINARY PROCEDIMENTS AND SANCTIONS) of the University Regulations for Students (D.R. 672 of 5/12/2017, which came into force on 8/12/2017).

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Introduction to the course.

Introduction to the Map-Reduce parallel programming model. Open-source Hadoop implementation. Pros and cons of Hadoop and Map-Reduce. Distributed File System. Chunk servers, Master node. Map Function. Sort and Shuffle. Reduce Function. Map Tasks. Reduce Tasks. Word counting. Handling failures. Number of Map and Reduce jobs. Granularity of tasks and pipelining. Strugglers tasks: mitigating the problem by spawning backup tasks. Combiners. Partition (hash) function. Additional examples of Map-Reduce: natural join, two-pass matrix multiply, single pass matrix multiply. Cost measures for Map-Reduce algorithms.

Frequent Pattern Mining. Discovery of association rules. Market-basket model. Examples of possible applications. Frequent itemsets. Support of an itemset. Association rules. Confidence and Interest. Association rules with highly positive or negative interest. Mining association rules. Maximal and closed frequent itemsets. Lattice of the itemsets. Naive approach to counting frequent pairs. A-priori. Monotonicity. PCY. PCY refinements: multistage and multihash. Frequent itemsets in 2 passes: random sampling and choice of the threshold, SON, monotonicity, parallel SON parallelo with Map-Reduce in 2 passes, Toivonen and the negative border. ECLAT. DECLAT. FPGrowth.  Sequence mining. Frequent sequences. Mining frequent sequences. GSP. SPADE. PREFIXSPAN. 

Streams. Uniform, 2-universal and pairwise independent hash function. Streaming: turnstile, strict turnstile and cash register models. Frequency estimation. Sketches. Count-Sketch. Count-Min. Comparing Count-Sketch and Count-Min. Frequent items. Phi-frequent items. The majority problem. Boyer-Moore. Misra-Gries. Frequent. Space Saving. Space Saving properties. Comparing Frequent and Space Saving. Sampling from a Data Stream: Sampling a fixed proportion. Sampling from a Data Stream: Sampling a fixed-size sample (Reserved Sampling). Queries over a sliding windows: counting the number of bits equal to 1 with DGIM. Filtering data streams: Bloom FIlters. Counting distinct elements: Flajolet-Martin. Estimating moments with AMS.

Scene completion problem. Near neighbors in high dimensionality spaces. Document similarity. Pairs of candidate documents. Near neighbor search. Jaccard similarity and distance. Shingling: how to convert documents, emails etc in sets. k-shingles. Compression through hashing of k-shingles. Min-Hashing: converting big sets in short signatures preserving the similarity. Similarity and Jaccard distance for boolean vectors. Boolean matrices. Min-hash signatures. Implementation. Locality-Sensitive Hashing: determining pairs of candidate documents. Matrix partitioning in b bands of r rows: analysis of accuracy with regard to  false positives and false negatives.

Link analysis. PageRank. Dead ends. Spider traps. Flow formulation. Matrix formulation. Random walk interpretation. Stationary distribution of a Discrete-Time Markov Chain. Perron-Frobenius Theorem. Google matrix and teleportation. Sparse matrix encoding. Block update algorithm. Topic-specific PageRank. Matrix formulation. Topic vector. Web Spam. Term spam. Spam farms. PageRank value obtained through a Spam Farm. TrustRank. Trust propagation. Spam Mass estimation.

Recommender systems. Recommendations. The long tail phenomenon. Content-based systems. Utility function and matrix. Ratings. Extrapolation of ratings (utilities). Item profiles. User profiles. Collaborative filtering. k-NN. Similarity metrics. User-user and item-item collaborative filtering. Evaluation of systems. Error metrics. RMSE, precision, rank correlation. Complexity of collaborative filtering. The Netflix challenge. Bellkor recommender system. Modeling local and global effects. Learning the optimal weights: optimization problem and gradient descent. Latent factor models. SVD decomposition. Learning the P and Q matrices. Preventing overfitting: regularization. Stochastic Gradient Descent. Biases and interactions. Temporal biases and factors.

Artificial Intelligence. Different definitions over time: thinking like a human, acting like humans and the Turing test, thinking rationally, acting rationally. Rational agents, decisions and behaviour. Game playing: chess, go, etc. The human intelligence. Human versus artificial intelligence. Benefits of AI. Ai, machine learning and deep learning. AI applications and use-cases. Human learning process. Features, instances, labels, classes, classification function. Training set, validation and test set. Supervised learning: regression, binary and multiclass classification. Unsupervised learning. Semi-supervised and weakly-supervised learning. Reinforcement learning: agent, environment and its state that changes depending on the agent's actions, reward and penalty. Loss functions. Zero-one and squared loss functions. Bias and variance. Deep Learning. Machine Learning vs Deep Learning. Limitations of Deep Learning. Artificial versus biological neural networks. AI Myths.

The clustering problem. Curse of dimensionality. Clustering in euclidean and non euclidean spaces. Distances. Hierarchical clustering: agglomerative and divisive algorithms. Clustering by point assignment. Centroid and clustroid. K-means and K-means++. Choosing k: elbow criterion. BFR. Discard, Compression and Retained sets. Summarizing points. Mahalanobis distance. CURE. Representative points and their choice. Input space and feature space. Kernel methods. Kernel matrix. Linear kernel. Kernel trick. Kernel operations in feature space. Represenative clustering: K-means and Kernel K-means. Expectation-Maximization clustering. Hierarchical clustering. Density-based clustering. DBSCAN. Clustering validation: external, internal and relative measures.

Machine learning. Supervised and unsupervised approaches. Numerical and categorical attributes. Categorical attributes: nominal and ordinal attributes. Probabilistic classifiers. Parametric approach: Bayes and naive Bayes classifiers. Data centering. Non parametric approach (density based): K-nearest neighbors classifier. Decision Trees. Hyperplans. Split points. Data partion and purity. Split Point Evaluation Measures: entropy, split entropy, information gain, Gini index, CART. Evaluation of numerical and categorical split points. Support Vector machines. Hyperplanes. Support Vectors and Margins. Linear and Separable Case. Soft Margin SVM: Linear and Nonseparable Case. Kernel SVM: Nonlinear Case. SVM Training Algorithms. Multiclass SVM. Assessing the performances of a classifier. Evaluation metrics. ROC curve and AUC. K-fold cross-validation. Bootstrapping. Confidence intervals. Paired t-Test. Bias and variance decomposition. Ensemble classifiers. Bagging. Random Forest. Boosting. Stacking.

Introduction to neural networks. History. The Biological Inspiration. Learning in Biological vs Artificial Networks. An Alternative View: The Computational Graph Extension of Traditional Machine Learning. Machine Learning versus Deep Learning. Single Layer Networks: the Perceptron. Bias neurons. Training a Perceptron. Perceptron vs Linear SVMs. Activation and Loss Functions. Multilayer Neural Networks. Reasons  for nonlinearity of hidden layers. Role of Hidden Layers. The Feature Engineering View of Hidden Layers. Multilayer Networks as Computational Graphs. Connecting Machine Learning with Shallow Neural Networks: Perceptron versus Linear SVM, RBF Network versus kernel SVM. Neural models for linear regression, classification and the Fisher discriminant. Widrow-Hoff learning. Neural model for linear regression. Comparison of Widrow-Hoff with Perceptron and SVM. Connections with Fisher Discriminant. Neural Models for Logistic Regression. The Softmax Activation Function and Multinomial Logistic Regression. The Autoencoder for Unsupervised Representation Learning. Singular Value Decomposition with Autoencoders. Row-Index to Row-Value Autoencoders: Incomplete Matrix Factorization for Recommender Systems. Model Generalization and the Bias-Variance Trade-Off in the context of neural networks. 

Penalty-Based Regularization. Economy in Parameters. Soft vs hard economy. L1 vs L2 regularization. L2 regularization and noise injection. Weight sharing. Dropout. Feature co-adaptation. Why feature co-adaptation is bad. Dropout training. Dropout testing: repeated sampling and geometric averaging vs weight scaling inference rule. Why dropout helps. Connection of dropout with noise injection and regularization. How to apply dropout in practice.

Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Freely availableonline: http://www.mmds.org

Data Mining and Analysis

M. J. Zaki and W. Meira

Freely available online: http://dataminingbook.info

Neural Networks and Deep Learning

Charu C. Aggarwal

Springer

Calculus I and II, Probability Theory. Programming skills and working knowledge of the C programming language.

The course provides a modern introduction to design, analysis and implementation of sequential and parallel algorithms. In particular, the course is based on a pragmatic approach to parallel programming of message-passing algorithms through the C language and the MPI library.

Knowledge and understanding. Students must have a solid background with a broad spectrum of basic knowledge of sequential and parallel algorithms:

· the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;

· they must have a solid knowledge of the design and implementation of sequential and parallel efficient algorithms;

· they must have the tools for analysing the resources used by algorithms;

· they must have a catalogue of the most well-known and efficient sequential and parallel algorithms for basic computational problems.

Applying knowledge and understanding. After the course the student should be able to:

· Describe and use the main design techniques for sequential algorithms;

· Design, prove the correctness and analyze the computational complexity of sequential algorithms;

· Understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;

· Describe and use basic sequential algorithms;

· Describe and use basic data structures; know about the existence of advanced data structures;

· Understand the difference between sequential and parallel algorithms;

· Design, implement and analyze message-passing based parallel algorithms in C using the MPI library;

· Describe and use basic parallel algorithms.

Making judgements. Students are guided to learn critically everything that is explained to them in class, to compare different approaches to solving algorithmic problems, and to identify and propose, in an autonomous way, the most efficient solution they find.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. The course promotes the development of the following skills of the student: ability to expose in precise and formal terms an abstract model of concrete problems, identifying the salient features of them and discarding the nonessential ones; ability to describe and analyze an efficient solution to the problem in question.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to enable students to abstract formal algorithmic models and problems from concrete computational problems, and to design efficient algorithmic solutions for them. This will be done using the following teaching method. Every computational problem will be introduced, motivating it with concrete examples. The presentation of each topic will be divided into four parts: 1. Description of the actual computational problem. 2. Modelling the real problem by means of an abstract problem. 3. Resolution of the abstract problem through an algorithm obtained through the application of the general techniques of design of algorithms introduced in the course. 4. Analysis of the resources used by the algorithm. The course consists of frontal lessons, and classroom exercises. There will be theoretical lessons aimed at learning the basic techniques for the project and analysis of algorithms, and a part of lessons devoted to exercises in which we will illustrate, with plenty of examples, how the theoretical knowledge acquired can be used in order to solve algorithmic problems of practical interest and implement parallel algorithms in C language through the MPI library.

The exam consists of a written test and a prototype implementation of a parallel software. The written test  (2 hours, 21 points out of 30) covers theoretical topics related to the design and analysis of sequential and parallel algorithms in order to verify the student’s knowledge and understanding of the materials. In order to pass the written test, students must obtain at least 9 points out of 21.  The parallel software project (9 points out of 30) is meant to verify the practice of parallel programming and the ability of the student to implement theoretical parallel algorithms or to parallelize a sequential algorithm. In order to pass the parallel programming challenge, students must obtain at least 4 points out of 9. Both the written test and the prototype implementation of parallel software are mandatory. Students must pass both the written test and the parallel programming challenge; however, the overall exam is passed only if the sum of points obtained in the written test and the parallel programming challenge is greater than or equal to 18 points.

The problem to be solved in parallel (or a sequential algorithm to be implemented in parallel) is assigned upon request to the student. The assigned parallel software project can be discussed only if a written test has been successfully passed; moreover, the parallel software project must be mandatorily discussed into the same trial in which the written test has been passed.

The report on the assigned parallel software project must be structured as follows.

1. Introduction. The student must provide an accurate description of the assigned project, including an analysis of the sequential algorithm that solves the problem addressed in the project. If the student deems it important for understanding, then pseudo-code, examples, graphs, figures, application instances etc. may be included; 

2. Parallel design. This is a preliminary study aimed at highlighting the opportunities for parallelism inherent in the problem and/or sequential algorithm. Starting from the pseudo-code, it is then necessary to determine the most appropriate functionalities, code parts and/or data structures that can be considered for parallelisation. At this stage, alternative designs for different parallelisation strategies must be considered and discussed, duly justifying why some operations lend themselves to effective parallelisation and others do not. Furthermore, the expected results must be reported, including a worst-case parallel complexity analysis. Clarity of exposition regarding the parallelisation strategy is required, therefore the data structures used must be described in full, justifying the choices made to minimise the burden of communication and synchronisation. The theoretical analytical evaluation of the scalability of the parallel version is mandatory, and must be performed using both the isoefficiency and the scalability function. 

3. Implementation. The parallel design adopted must be implemented using the programming language C or, possibly, C++ (so as to use the data structures present in the STL of C++). The code must necessarily be appropriately commented. In the event that the student verifies the existence of multiple parallelisation strategies for the same assigned problem, an implementation can be provided for each strategy, discussing the advantages and disadvantages of each strategy. Note that the parallel code does not have to be given in full in the text of the report, as the project code - source and Makefile for the build (alternatively CMake can be used) - must in any case be delivered separately. However, the report may include some code snippets relating to the most critical and interesting parts.

4. Debugging and testing. Debugging and testing of the parallel code is recommended in order to reasonably verify the absence of bugs and the correctness of the parallel algorithm in relation to the output produced. The student is encouraged to design and verify unit tests deemed suitable for assessing the goodness of the code. The student is explicitly warned that the implementation of an incorrect parallelisation strategy and/or the presence of bugs that crash the parallel application at runtime will result in failing the exam, while the presence of bugs that affect the correctness of the algorithm will result in a penalty relative to the mark that will be awarded. 

5. Performance and scalability analysis. The student must analyse the performance of the developed implementation in terms of execution time, memory occupation (if necessary), speedup and efficiency. Both strong scalability (Amdahl) and weak scalability (Gustafson) must be assessed where possible. 

6. Synthesis. The report must be as concise as possible, but without detriment to clarity of presentation. 

7. Project evaluation. The project will be assessed on a scale of 1 to 9 points. The grade will only be determined at the end of the project discussion. The complexity of the problem assigned will be taken into account in the evaluation; students dealing with simpler problems should therefore expect less leniency in the evaluation than students dealing with more difficult problems. 

Assessment will also take into account: 

- Clarity and effectiveness of presentation; 

- Depth, correctness and originality of theoretical analysis; 

- Technical ability and documentation of implementation; 

- Number and quality of multiple parallel strategies, if any; 

- Critical thinking in performance evaluation and analysis; 

Significance of results: since parallel programming is primarily concerned with performance, a good project must also provide a significant speedup.

8. Plagiarism. The student is explicitly warned that plagiarism is very serious, and is taken very seriously. The use of external sources of any kind (internet, books, handouts, previous work by other students etc.) is only allowed for marginal contributions in the project (e.g. for the initial description of the assigned project), and each individual occurrence must be explicitly cited and reported in the report. Violation of this code of conduct will not be tolerated in any way, and will result in the immediate cancellation of the examination and the referral of the student to the University Disciplinary Committee, with the commencement of the relevant disciplinary proceedings in accordance with the provisions of Title V (DISCIPLINARY PROCEDIMENTS AND SANCTIONS) of the University Regulations for Students (D.R. 672 of 5/12/2017, which came into force on 8/12/2017).

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Parallel Algorithms

Introduction. Parallel Architectures. Parallel algorithm design. Message-Passing Programming. Sieve of Erathostenes. Floyd all-pairs shortest path algorithm. Performance analysis. Matrix-vector multiplication. Document classification. Matrix multiplication. Linear Systems. Finite Difference Methods. Sorting. 

Parallel Programming

Message-Passing programming using MPI.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer. Divide and conquer. Recurrences. Randomized algorithms. Transform and conquer.  Dynamic programming. Greedy algorithms. Single Source Shortest Paths. Dijkstra algorithm. Breadth-First Search. Bellman-Ford Algorithm. Complexity and computability. NP-Completeness. The transition from sequential to parallel computing. Parallel complexity.

Introduction to Algorithms. Fourth edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP (International Edition). Michael J. Quinn. McGraw-Hill

Calculus. Probability theory. Linear Algebra. Programming skills.

The course provides a modern introduction to data mining, which spans techniques, algorithms and methodologies for discovering structure, patterns and relationships in data sets (typically, large ones) and making predictions. Applications of data mining are already happening all around us, and, when they are done well, sometimes they even go unnoticed. For instance, how does the Google web search work? How does Shazam recognize a song? How does Netflix recommend movies to its users? The principles of data mining provide answers to these and others questions. Data mining overlaps the fields of computer science, statistical machine learning and data bases. The course aims at providing the students with the knowldedge required to explore, analyze and leverage available data in order to turn the data into valuable and actionable information for a company, for instance, in order to facilitate a decision-making process.

Knowledge and understanding. The course describes methods and models for the analysis of large amounts of data. Students must have a solid background with a broad spectrum of basic knowledge related to data mining:

• the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;
• they must have solid knowledge of data mining models and methodologies;
• they must be able to work on large data collections, including heterogeneous and produced at high speed data, in order to integrate them - in particular by knowing how to manage their origin and quality - and to carry out in-depth thematic analyses, drawing on this knowledge to improve the decision-making process.

Applying knowledge and understanding. After the course the student should be able to:

• describe and use the main data mining techniques;
• understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;
• tackle new data mining problems by selecting the appropriate methods and justifying his/her choices;
• tackle new data mining problems by designing suitable algorithms and evaluating the results;
• explain experimental results to people outside of statistical machine learning or computer science.

Making judgements. Students must have the ability to process complex and/or fragmentary data and must arrive at original and autonomous ideas and judgments, and consistent choices in the context of their work, which are particularly delicate in the profession of data scientist. The course promotes the development of independent judgment in the appropriate choice of technique/model for data processing and the critical ability to interpret the goodness of the results of the models/methods applied to the datasets under examination.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. Students should be able to organize effective dissemination and study material through the most common presentation tools, including computer-based ones, to communicate the results of data analysis processes, for example by using visualization and reporting tools aimed at different types of audiences.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to provide students with advanced tools for data analysis, through which to extrapolate relevant information from large datasets and guide the related decision-making processes. The course consists of frontal lessons using slides made available to students via the Moodle platform, and classroom exercises. The frontal lessons are aimed at improving students' knowledge and understanding through the presentation of theories, models and methods; students are invited to participate in the lesson with autonomy of judgement, by asking questions and presenting examples. The exercises are aimed at understanding the algorithms and models presented.

Oral exam. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student must demonstrate adequate knowledge and understanding of the issues presented or indicated, applying in a relevant manner the theories and conceptual models covered by the study programme.

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Introduzione al corso. Streams. Funzioni hash uniformi, 2-universal e pairwise independent. Streaming: modello turnstile, strict turnstile e cash register. Frequency estimation. Sketches. Count-Sketch. Count-Min. Confronto comparativo tra Count-Sketch e Count-Min. Frequent items. Phi-frequent items. The majority problem. Algoritmo di Boyer-Moore. Algoritmo di Misra-Gries. Algoritmo Frequent.Algoritmo Space Saving. Proprieta' di Space Saving. Confronto comparativo con Frequent. Introduzione al paradigma di programmazione parallela Map-Reduce. Implementazione open-source Hadoop. Pro e contro di Hadoop e Map-Reduce. Distributed File System. Chunk servers, Master node. Map Function. Sort and Shuffle. Reduce Function. Map Tasks. Reduce Tasks. Word counting. Gestione dei guasti. Numero di Map e Reduce jobs. Granularita' dei tasks e pipelining. Mitigare il problema degli strugglers task: spawning di backup tasks. Combiners. Partition (hash) function. Altri esempi di algoritmi Map-Reduce: natural join, two-pass matrix multiply, single pass matrix multiply. Misure di costo per un algoritmo Map-Reduce. Discovery di association rules. Modello market-basket. Esempi di possibili applicazioni. Frequent itemsets. Supporto di un itemset. Association rules. Confidence e Interest.Association rules con elevato interesse positivo o negativo. Mining di association rules. Maximal e closed frequent itemsets. Lattice degli itemsets. Naive approach to counting frequent pairs. Algoritmo A-priori. Monotonicity. Algoritmo PCY. Raffinamenti di PCY: multistage e multihash. Frequent itemsets in 2 passate: random sampling. Frequent itemsets in 2 passate: Random sampling e scelta della soglia opportuna, algoritmo SON, monotonicità, SON parallelo mediante Map-Reduce in 2 passate, algoritmo di Toivonen, bordo negativo. Scene completion problem. Near neighbors in spazi di dimensionalità elevata. Document similarity. Coppie di documenti candidati. Near neighbor search. Jaccard similarity e distance. Shingling: convertire documenti email etc in insiemi. k-shingles. Compressione mediante hashing di k-shingles. Min-Hashing: conversione di insiemi di cardinalità elevata in brevi signatures preservando la similarità. Similarità e distanza di Jaccard per vettori booleani. Boolean matrices. Min-hash signatures. Implementazione. Locality-Sensitive Hashing: determinare coppie di documenti candidate. Matrix partitioning in b bande di r righe: analisi del grado di accuratezza associato rispetto ai falsi positivi ed ai falsi negativi. Link analysis. PageRank. Dead ends. Spider traps. Flow formulation. Matrix formulation. Random walk interpretation. Stationary distribution of a Discrete-Time Markov Chain. Perron-Frobenius Theorem. Google matrix and teleportation. Sparse matrix encoding. Block update algorithm. Topic-specific PageRank. Matrix formulation. Topic vector. Web Spam. Term spam. Spam farms. Analisi del valore di PageRank ottenuto tramite Spam Farm. TrustRank. Trust propagation. Spam Mass estimation. Introduzione al problema del clustering. Curse of dimensionality. Clustering in spazi euclidei e non euclidei. Distanze. Hierarchical clustering: agglomerative and divisive algorithms. Clustering by point assignment. Centroid and clustroid. K-means e K-means++. Scelta di k: elbow criterion. Algoritmo BFR. Discard, Compression e Retained sets. Summarizing points. Distanza di Mahalanobis. Algoritmo CURE. Punti rappresentativi e loro scelta. Input space e feature space. Kernel methods. Kernel matrix. Linear kernel. Kernel trick. Kernel operations in feature space. Represenattive clustering: K-means e Kernel K-means. Expectation-Maximization clustering. Hierarchical clustering. Density-based clustering. Algoritmo DBSCAN. Recommender systems. Recommendations. The long tail phenomenon. Content-based systems. Utility function and matrix. Ratings. Extrapolation of ratings (utilities). Item profiles. User profiles. Collaborative filtering. k-NN. Similarity metrics. User-user and item-item collaborative filtering. Evaluation of systems. Error metrics. RMSE, precision, rank correlation. Complexity of collaborative filtering. The Netflix challenge. Bellkor recommender system. Modeling local and global effects. Learning the optimal weights: optimization problem and gradient descent. Latent factor models. SVD decomposition. Learning the P and Q matrices. Preventing overfitting: regularization. Stochastic Gradient Descent. Biases and interactions. Temporal biases and factors. Machine learning: supervised and unsupervised approaches. Attributi numerici e categorici. Attributi categorici nominali ed ordinali. Probabilistic classifiers. Parametric approach: Bayes and naive Bayes classifiers. Data centering. Non parametric approach (density based): K-nearest neighbors classifier. Decision Trees. Hyperplans. Split points. Data partion and purity. Split Point Evaluation Measures: entropy, split entropy, information gain, Gini index, CART. Valutazione di split points numerici e categorici. Support Vector machines. Hyperplanes. Support Vectors and Margins. Linear and Separable Case. Soft Margin SVM: Linear and Nonseparable Case. Kernel SVM: Nonlinear Case. SVM Training Algorithms. Multiclass SVM. Analisi delle prestazioni di un classifier. Metriche di valutazione. ROC curve e AUC. K-fold cross-validation. Bootstrapping. Intervalli di confidenza. Paired t-Test. Bias and variance decomposition. Ensemble classifiers. Bagging. Random Forest. Boosting. Stacking. Introduction to neural networks. History. The Biological Inspiration. Learning in Biological vs Artificial Networks. An Alternative View: The Computational Graph Extension of Traditional Machine Learning. Machine Learning versus Deep Learning. Single Layer Networks: the Perceptron. Bias neurons. Training a Perceptron. Perceptron vs Linear SVMs. Activation and Loss Functions. Multilayer Neural Networks. Reasons  for nonlinearity of hidden layers. Role of Hidden Layers. The Feature Engineering View of Hidden Layers. Multilayer Networks as Computational Graphs. Connecting Machine Learning with Shallow Neural Networks: Perceptron versus Linear SVM, RBF Network versus kernel SVM.

Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Freely availableonline: http://www.mmds.org

Data Mining and Analysis

M. J. Zaki and W. Meira

Freely available online: http://dataminingbook.info

Neural Networks and Deep Learning

Charu C. Aggarwal

Springer

Calculus I and II, Probability Theory. Programming skills and working knowledge of the C programming language.

The course provides a modern introduction to design, analysis and implementation of sequential and parallel algorithms. In particular, the course is based on a pragmatic approach to parallel programming of message-passing algorithms through the C language and the MPI library.

Knowledge and understanding. Students must have a solid background with a broad spectrum of basic knowledge of sequential and parallel algorithms:

· the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;

· they must have a solid knowledge of the design and implementation of sequential and parallel efficient algorithms;

· they must have the tools for analysing the resources used by algorithms;

· they must have a catalogue of the most well-known and efficient sequential and parallel algorithms for basic computational problems.

Applying knowledge and understanding. After the course the student should be able to:

· Describe and use the main design techniques for sequential algorithms;

· Design, prove the correctness and analyze the computational complexity of sequential algorithms;

· Understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;

· Describe and use basic sequential algorithms;

· Describe and use basic data structures; know about the existence of advanced data structures;

· Understand the difference between sequential and parallel algorithms;

· Design, implement and analyze message-passing based parallel algorithms in C using the MPI library;

· Describe and use basic parallel algorithms.

Making judgements. Students are guided to learn critically everything that is explained to them in class, to compare different approaches to solving algorithmic problems, and to identify and propose, in an autonomous way, the most efficient solution they find.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. The course promotes the development of the following skills of the student: ability to expose in precise and formal terms an abstract model of concrete problems, identifying the salient features of them and discarding the nonessential ones; ability to describe and analyze an efficient solution to the problem in question.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to enable students to abstract formal algorithmic models and problems from concrete computational problems, and to design efficient algorithmic solutions for them. This will be done using the following teaching method. Every computational problem will be introduced, motivating it with concrete examples. The presentation of each topic will be divided into four parts: 1. Description of the actual computational problem. 2. Modelling the real problem by means of an abstract problem. 3. Resolution of the abstract problem through an algorithm obtained through the application of the general techniques of design of algorithms introduced in the course. 4. Analysis of the resources used by the algorithm. The course consists of frontal lessons, and classroom exercises. There will be theoretical lessons aimed at learning the basic techniques for the project and analysis of algorithms, and a part of lessons devoted to exercises in which we will illustrate, with plenty of examples, how the theoretical knowledge acquired can be used in order to solve algorithmic problems of practical interest and implement parallel algorithms in C language through the MPI library.

The exam consists of a written test and a prototype implementation of a parallel software. The written test  (3 hours, 21 points out of 30) covers theoretical topics related to the design and analysis of sequential and parallel algorithms in order to verify the student’s knowledge and understanding of the materials. In order to pass the written test, students must obtain at least 9 points out of 21.  The parallel software project (9 points out of 30) is meant to verify the practice of parallel programming and the ability of the student to implement theoretical parallel algorithms or to parallelize a sequential algorithm. In order to pass the parallel programming challenge, students must obtain at least 4 points out of 9. Both the written test and the prototype implementation of parallel software are mandatory. Students must pass both the written test and the parallel programming challenge; however, the overall exam is passed only if the sum of points obtained in the written test and the parallel programming challenge is greater to or equal to 18 points.

The problem to be solved in parallel (or a sequential algorithm to be implemented in parallel) is assigned upon request to the student. The assigned parallel software project can be discussed only if a written test has been successfully passed; moreover, the parallel software project must be mandatorily discussed into one of the trials available in the same exam session in which the written test has been passed.

WARNING: THE FOLLOWING ARE DETAILED INSTRUCTIONS RELATED TO ONLINE WRITTEN TESTS USING MICROSOFT TEAMS 

Written test of 
Parallel Algorithms
 

Microsoft Teams is used to verify the student's identity and to supervise the test; the teacher will select each student asking him to show his identification document. The exam takes place within a team that students access through registration by the teacher or through a link that will be communicated via email. Students are asked to enter the team at least 15 minutes prior to the scheduled start time in order to perform recognition. Each student will participate in the meeting through a device equipped with a microphone and a webcam that must remain on for the duration of the test, framing the student and the paper on which he/she writes. The teacher will check the regularity of the students' work, immediately cancelling the test in case of irregularities of any kind.

For the distribution of the exam outline to the students, the teacher shares a pdf file in the TEAMS chat. The track is divided into 3 exercises for Parallel Algorithms, and the teacher releases to the students each of the exercises that compose it at fixed time intervals. The test is then carried out as follows:

1. The teacher releases the first exercise at the beginning of the roll call;
a. students print out the text of the exercise and begin drafting the paper on a sheet of paper clearly visible from the video capture device;
b. the teacher provides his/her estimate x of sufficient time to answer;
c. delivery of the paper related to the first exercise after x amount of time has elapsed;
d. Teacher waits 2 minutes for delivery;

2. Teacher delivers the second exercise;
a. students print out the text of the exercise and begin writing the paper on a sheet of paper clearly visible from the video capture device;
b. teacher gives his estimate y of sufficient time to answer;
c. delivery of the paper related to the second exercise after the time y has elapsed;
d. The teacher waits 2 minutes for the delivery;

3. Teacher releases the third exercise;
a. students print out the text of the exercise and begin writing the paper on a piece of paper that is clearly visible from the video capture device;
b. teacher gives his estimate z of sufficient time to answer;
c. delivery of the paper related to the second exercise after the time z has elapsed;
d. The teacher waits 2 minutes for the delivery;

4. The teacher informs the participating students that the roll call is closed.
  
For the delivery of the papers related to the individual exercises, the student is requested to take a photo of the relative sheets, including an image of the university booklet or, alternatively, an identification document. The photos should be placed in a directory called "Exercise_a_b_c_d" in which:

- a indicates the progressive number of the exercise (1, 2 or 3);
- b is PA  (for Parallel Algorithms)
- c indicates the student's first name;
- d indicates the student's last name.

The directory must then be compressed, e.g. in zip format, and the resulting file must be delivered via team chat.

It is not possible to turn in an exercise before the allotted time and move on to the next exercise. The student who intends to abandon the test can give notice to the teacher at any time, and leave the team immediately afterwards. It is not possible to leave for any reason during the test. The student is required to ensure that he/she has everything necessary for the test (microphone, webcam, printer, camera, pen, adequate number of sheets of paper).

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Parallel Algorithms

Introduction. Parallel Architectures. Parallel algorithm design. Message-Passing Programming. Sieve of Erathostenes. Floyd all-pairs shortest path algorithm. Performance analysis. Matrix-vector multiplication. Document classification. Matrix multiplication. Linear Systems. Finite Difference Methods. Sorting. 

Parallel Programming

Message-Passing programming using MPI.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer. Divide and conquer. Recurrences. Randomized algorithms. Transform and conquer.  Dynamic programming. Greedy algorithms. Single Source Shortest Paths. Dijkstra algorithm. Breadth-First Search. Bellman-Ford Algorithm. Complexity and computability. NP-Completeness. The transition from sequential to parallel computing. Parallel complexity.

Introduction to Algorithms. Third edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP (International Edition). Michael J. Quinn. McGraw-Hill

Calculus. Probability theory. Linear Algebra. Programming skills.

The course provides a modern introduction to data mining, which spans techniques, algorithms and methodologies for discovering structure, patterns and relationships in data sets (typically, large ones) and making predictions. Applications of data mining are already happening all around us, and, when they are done well, sometimes they even go unnoticed. For instance, how does the Google web search work? How does Shazam recognize a song? How does Netflix recommend movies to its users? The principles of data mining provide answers to these and others questions. Data mining overlaps the fields of computer science, statistical machine learning and data bases. The course aims at providing the students with the knowldedge required to explore, analyze and leverage available data in order to turn the data into valuable and actionable information for a company, for instance, in order to facilitate a decision-making process.

Knowledge and understanding. The course describes methods and models for the analysis of large amounts of data. Students must have a solid background with a broad spectrum of basic knowledge related to data mining:

• the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;
• they must have solid knowledge of data mining models and methodologies;
• they must be able to work on large data collections, including heterogeneous and produced at high speed data, in order to integrate them - in particular by knowing how to manage their origin and quality - and to carry out in-depth thematic analyses, drawing on this knowledge to improve the decision-making process.

Applying knowledge and understanding. After the course the student should be able to:

• describe and use the main data mining techniques;
• understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;
• tackle new data mining problems by selecting the appropriate methods and justifying his/her choices;
• tackle new data mining problems by designing suitable algorithms and evaluating the results;
• explain experimental results to people outside of statistical machine learning or computer science.

Making judgements. Students must have the ability to process complex and/or fragmentary data and must arrive at original and autonomous ideas and judgments, and consistent choices in the context of their work, which are particularly delicate in the profession of data scientist. The course promotes the development of independent judgment in the appropriate choice of technique/model for data processing and the critical ability to interpret the goodness of the results of the models/methods applied to the datasets under examination.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. Students should be able to organize effective dissemination and study material through the most common presentation tools, including computer-based ones, to communicate the results of data analysis processes, for example by using visualization and reporting tools aimed at different types of audiences.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to provide students with advanced tools for data analysis, through which to extrapolate relevant information from large datasets and guide the related decision-making processes. The course consists of frontal lessons using slides made available to students via the Moodle platform, and classroom exercises. The frontal lessons are aimed at improving students' knowledge and understanding through the presentation of theories, models and methods; students are invited to participate in the lesson with autonomy of judgement, by asking questions and presenting examples. The exercises are aimed at understanding the algorithms and models presented.

Oral exam. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student must demonstrate adequate knowledge and understanding of the issues presented or indicated, applying in a relevant manner the theories and conceptual models covered by the study programme.

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Introduzione al corso. Streams. Funzioni hash uniformi, 2-universal e pairwise independent. Streaming: modello turnstile, strict turnstile e cash register. Frequency estimation. Sketches. Count-Sketch. Count-Min. Confronto comparativo tra Count-Sketch e Count-Min. Frequent items. Phi-frequent items. The majority problem. Algoritmo di Boyer-Moore. Algoritmo di Misra-Gries. Algoritmo Frequent.Algoritmo Space Saving. Proprieta' di Space Saving. Confronto comparativo con Frequent. Introduzione al paradigma di programmazione parallela Map-Reduce. Implementazione open-source Hadoop. Pro e contro di Hadoop e Map-Reduce. Distributed File System. Chunk servers, Master node. Map Function. Sort and Shuffle. Reduce Function. Map Tasks. Reduce Tasks. Word counting. Gestione dei guasti. Numero di Map e Reduce jobs. Granularita' dei tasks e pipelining. Mitigare il problema degli strugglers task: spawning di backup tasks. Combiners. Partition (hash) function. Altri esempi di algoritmi Map-Reduce: natural join, two-pass matrix multiply, single pass matrix multiply. Misure di costo per un algoritmo Map-Reduce. Discovery di association rules. Modello market-basket. Esempi di possibili applicazioni. Frequent itemsets. Supporto di un itemset. Association rules. Confidence e Interest.Association rules con elevato interesse positivo o negativo. Mining di association rules. Maximal e closed frequent itemsets. Lattice degli itemsets. Naive approach to counting frequent pairs. Algoritmo A-priori. Monotonicity. Algoritmo PCY. Raffinamenti di PCY: multistage e multihash. Frequent itemsets in 2 passate: random sampling. Frequent itemsets in 2 passate: Random sampling e scelta della soglia opportuna, algoritmo SON, monotonicità, SON parallelo mediante Map-Reduce in 2 passate, algoritmo di Toivonen, bordo negativo. Scene completion problem. Near neighbors in spazi di dimensionalità elevata. Document similarity. Coppie di documenti candidati. Near neighbor search. Jaccard similarity e distance. Shingling: convertire documenti email etc in insiemi. k-shingles. Compressione mediante hashing di k-shingles. Min-Hashing: conversione di insiemi di cardinalità elevata in brevi signatures preservando la similarità. Similarità e distanza di Jaccard per vettori booleani. Boolean matrices. Min-hash signatures. Implementazione. Locality-Sensitive Hashing: determinare coppie di documenti candidate. Matrix partitioning in b bande di r righe: analisi del grado di accuratezza associato rispetto ai falsi positivi ed ai falsi negativi. Link analysis. PageRank. Dead ends. Spider traps. Flow formulation. Matrix formulation. Random walk interpretation. Stationary distribution of a Discrete-Time Markov Chain. Perron-Frobenius Theorem. Google matrix and teleportation. Sparse matrix encoding. Block update algorithm. Topic-specific PageRank. Matrix formulation. Topic vector. Web Spam. Term spam. Spam farms. Analisi del valore di PageRank ottenuto tramite Spam Farm. TrustRank. Trust propagation. Spam Mass estimation. Introduzione al problema del clustering. Curse of dimensionality. Clustering in spazi euclidei e non euclidei. Distanze. Hierarchical clustering: agglomerative and divisive algorithms. Clustering by point assignment. Centroid and clustroid. K-means e K-means++. Scelta di k: elbow criterion. Algoritmo BFR. Discard, Compression e Retained sets. Summarizing points. Distanza di Mahalanobis. Algoritmo CURE. Punti rappresentativi e loro scelta. Input space e feature space. Kernel methods. Kernel matrix. Linear kernel. Kernel trick. Kernel operations in feature space. Represenattive clustering: K-means e Kernel K-means. Expectation-Maximization clustering. Hierarchical clustering. Density-based clustering. Algoritmo DBSCAN. Recommender systems. Recommendations. The long tail phenomenon. Content-based systems. Utility function and matrix. Ratings. Extrapolation of ratings (utilities). Item profiles. User profiles. Collaborative filtering. k-NN. Similarity metrics. User-user and item-item collaborative filtering. Evaluation of systems. Error metrics. RMSE, precision, rank correlation. Complexity of collaborative filtering. The Netflix challenge. Bellkor recommender system. Modeling local and global effects. Learning the optimal weights: optimization problem and gradient descent. Latent factor models. SVD decomposition. Learning the P and Q matrices. Preventing overfitting: regularization. Stochastic Gradient Descent. Biases and interactions. Temporal biases and factors. Machine learning: supervised and unsupervised approaches. Attributi numerici e categorici. Attributi categorici nominali ed ordinali. Probabilistic classifiers. Parametric approach: Bayes and naive Bayes classifiers. Data centering. Non parametric approach (density based): K-nearest neighbors classifier. Decision Trees. Hyperplans. Split points. Data partion and purity. Split Point Evaluation Measures: entropy, split entropy, information gain, Gini index, CART. Valutazione di split points numerici e categorici. Support Vector machines. Hyperplanes. Support Vectors and Margins. Linear and Separable Case. Soft Margin SVM: Linear and Nonseparable Case. Kernel SVM: Nonlinear Case. SVM Training Algorithms. Multiclass SVM. Analisi delle prestazioni di un classifier. Metriche di valutazione. ROC curve e AUC. K-fold cross-validation. Bootstrapping. Intervalli di confidenza. Paired t-Test. Bias and variance decomposition. Ensemble classifiers. Bagging. Random Forest. Boosting. Stacking. Introduction to neural networks. History. The Biological Inspiration. Learning in Biological vs Artificial Networks. An Alternative View: The Computational Graph Extension of Traditional Machine Learning. Machine Learning versus Deep Learning. Single Layer Networks: the Perceptron. Bias neurons. Training a Perceptron. Perceptron vs Linear SVMs. Activation and Loss Functions. Multilayer Neural Networks. Reasons  for nonlinearity of hidden layers. Role of Hidden Layers. The Feature Engineering View of Hidden Layers. Multilayer Networks as Computational Graphs. Connecting Machine Learning with Shallow Neural Networks: Perceptron versus Linear SVM, RBF Network versus kernel SVM.

Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Freely availableonline: http://www.mmds.org

Data Mining and Analysis

M. J. Zaki and W. Meira

Freely available online: http://dataminingbook.info

Neural Networks and Deep Learning

Charu C. Aggarwal

Springer

Calculus I and II, Probability Theory. Programming skills and working knowledge of the C programming language.

The course provides a modern introduction to design, analysis and implementation of sequential and parallel algorithms. In particular, the course is based on a pragmatic approach to parallel programming of message-passing algorithms through the C language and the MPI library.

Knowledge and understanding. Students must have a solid background with a broad spectrum of basic knowledge of sequential and parallel algorithms:

· the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;

· they must have a solid knowledge of the design and implementation of sequential and parallel efficient algorithms;

· they must have the tools for analysing the resources used by algorithms;

· they must have a catalogue of the most well-known and efficient sequential and parallel algorithms for basic computational problems.

Applying knowledge and understanding. After the course the student should be able to:

· Describe and use the main design techniques for sequential algorithms;

· Design, prove the correctness and analyze the computational complexity of sequential algorithms;

· Understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;

· Describe and use basic sequential algorithms;

· Describe and use basic data structures; know about the existence of advanced data structures;

· Understand the difference between sequential and parallel algorithms;

· Design, implement and analyze message-passing based parallel algorithms in C using the MPI library;

· Describe and use basic parallel algorithms.

Making judgements. Students are guided to learn critically everything that is explained to them in class, to compare different approaches to solving algorithmic problems, and to identify and propose, in an autonomous way, the most efficient solution they find.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. The course promotes the development of the following skills of the student: ability to expose in precise and formal terms an abstract model of concrete problems, identifying the salient features of them and discarding the nonessential ones; ability to describe and analyze an efficient solution to the problem in question.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to enable students to abstract formal algorithmic models and problems from concrete computational problems, and to design efficient algorithmic solutions for them. This will be done using the following teaching method. Every computational problem will be introduced, motivating it with concrete examples. The presentation of each topic will be divided into four parts: 1. Description of the actual computational problem. 2. Modelling the real problem by means of an abstract problem. 3. Resolution of the abstract problem through an algorithm obtained through the application of the general techniques of design of algorithms introduced in the course. 4. Analysis of the resources used by the algorithm. The course consists of frontal lessons, and classroom exercises. There will be theoretical lessons aimed at learning the basic techniques for the project and analysis of algorithms, and a part of lessons devoted to exercises in which we will illustrate, with plenty of examples, how the theoretical knowledge acquired can be used in order to solve algorithmic problems of practical interest and implement parallel algorithms in C language through the MPI library.

The exam consists of a written test and a prototype implementation of a parallel software. The written test  (3 hours, 21 points out of 30) covers theoretical topics related to the design and analysis of sequential and parallel algorithms in order to verify the student’s knowledge and understanding of the materials. In order to pass the written test, students must obtain at least 14 points out of 21.  The parallel software prototype (9 points out of 30) is meant to verify the practice of parallel programming and the ability of the student to implement theoretical parallel algorithms or to parallelize a sequential algorithm. In order to pass the parallel programming challenge, students must obtain at least 4 points out of 9. Both the written test and the prototype implementation of parallel software are mandatory. Students must pass both the written test and the parallel programming challenge.

WARNING: THE FOLLOWING ARE DETAILED INSTRUCTIONS RELATED TO ONLINE WRITTEN TESTS USING MICROSOFT TEAMS 

Written test of 
Parallel Algorithms
 

Microsoft Teams is used to verify the student's identity and to supervise the test; the teacher will select each student asking him to show his identification document. The exam takes place within a team that students access through registration by the teacher or through a link that will be communicated via email. Students are asked to enter the team at least 15 minutes prior to the scheduled start time in order to perform recognition. Each student will participate in the meeting through a device equipped with a microphone and a webcam that must remain on for the duration of the test, framing the student and the paper on which he/she writes. The teacher will check the regularity of the students' work, immediately cancelling the test in case of irregularities of any kind.

For the distribution of the exam outline to the students, the teacher shares a pdf file in the TEAMS chat. The track is divided into 3 exercises for Parallel Algorithms, and the teacher releases to the students each of the exercises that compose it at fixed time intervals. The test is then carried out as follows:

1. The teacher releases the first exercise at the beginning of the roll call;
a. students print out the text of the exercise and begin drafting the paper on a sheet of paper clearly visible from the video capture device;
b. the teacher provides his/her estimate x of sufficient time to answer;
c. delivery of the paper related to the first exercise after x amount of time has elapsed;
d. Teacher waits 2 minutes for delivery;

2. Teacher delivers the second exercise;
a. students print out the text of the exercise and begin writing the paper on a sheet of paper clearly visible from the video capture device;
b. teacher gives his estimate y of sufficient time to answer;
c. delivery of the paper related to the second exercise after the time y has elapsed;
d. The teacher waits 2 minutes for the delivery;

3. Teacher releases the third exercise;
a. students print out the text of the exercise and begin writing the paper on a piece of paper that is clearly visible from the video capture device;
b. teacher gives his estimate z of sufficient time to answer;
c. delivery of the paper related to the second exercise after the time z has elapsed;
d. The teacher waits 2 minutes for the delivery;

4. The teacher informs the participating students that the roll call is closed.
  
For the delivery of the papers related to the individual exercises, the student is requested to take a photo of the relative sheets, including an image of the university booklet or, alternatively, an identification document. The photos should be placed in a directory called "Exercise_a_b_c_d" in which:

- a indicates the progressive number of the exercise (1, 2 or 3);
- b is PA  (for Parallel Algorithms)
- c indicates the student's first name;
- d indicates the student's last name.

The directory must then be compressed, e.g. in zip format, and the resulting file must be delivered via team chat.

It is not possible to turn in an exercise before the allotted time and move on to the next exercise. The student who intends to abandon the test can give notice to the teacher at any time, and leave the team immediately afterwards. It is not possible to leave for any reason during the test. The student is required to ensure that he/she has everything necessary for the test (microphone, webcam, printer, camera, pen, adequate number of sheets of paper).

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Parallel Algorithms

Introduction. Parallel Architectures. Parallel algorithm design. Message-Passing Programming. Sieve of Erathostenes. Floyd all-pairs shortest path algorithm. Performance analysis. Matrix-vector multiplication. Document classification. Matrix multiplication. Linear Systems. Finite Difference Methods. Sorting. 

Parallel Programming

Message-Passing programming using MPI.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer. Divide and conquer. Recurrences. Randomized algorithms. Transform and conquer.  Dynamic programming. Greedy algorithms. Single Source Shortest Paths. Dijkstra algorithm. Breadth-First Search. Bellman-Ford Algorithm. Complexity and computability. NP-Completeness. The transition from sequential to parallel computing. Parallel complexity.

Introduction to Algorithms. Third edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP (International Edition). Michael J. Quinn. McGraw-Hill

Calculus. Probability and Statistics. Linear Algebra. Programming skills.

The course provides a modern introduction to data mining, which spans techniques, algorithms and methodologies for discovering structure, patterns and relationships in data sets (typically, large ones) and making predictions. Applications of data mining are already happening all around us, and, when they are done well, sometimes they even go unnoticed. For instance, how does the Google web search work? How does Shazam recognize a song? How does Netflix recommend movies to its users? The principles of data mining provide answers to these and others questions. Data mining overlaps the fields of computer science, statistical machine learning and data bases. The course aims at providing the students with the knowldedge required to explore, analyze and leverage available data in order to turn the data into valuable and actionable information for a company, for instance, in order to facilitate a decision-making process.

Knowledge and understanding. The course describes methods and models for the analysis of large amounts of data. Students must have a solid background with a broad spectrum of basic knowledge related to data mining:

• the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;
• they must have solid knowledge of data mining models and methodologies;
• they must be able to work on large data collections, including heterogeneous and produced at high speed data, in order to integrate them - in particular by knowing how to manage their origin and quality - and to carry out in-depth thematic analyses, drawing on this knowledge to improve the decision-making process.

Applying knowledge and understanding. After the course the student should be able to:

• describe and use the main data mining techniques;
• understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;
• tackle new data mining problems by selecting the appropriate methods and justifying his/her choices;
• tackle new data mining problems by designing suitable algorithms and evaluating the results;
• explain experimental results to people outside of statistical machine learning or computer science.

Making judgements. Students must have the ability to process complex and/or fragmentary data and must arrive at original and autonomous ideas and judgments, and consistent choices in the context of their work, which are particularly delicate in the profession of data scientist. The course promotes the development of independent judgment in the appropriate choice of technique/model for data processing and the critical ability to interpret the goodness of the results of the models/methods applied to the datasets under examination.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. Students should be able to organize effective dissemination and study material through the most common presentation tools, including computer-based ones, to communicate the results of data analysis processes, for example by using visualization and reporting tools aimed at different types of audiences.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to provide students with advanced tools for data analysis, through which to extrapolate relevant information from large datasets and guide the related decision-making processes. The course consists of frontal lessons using slides made available to students via the Moodle platform, and classroom exercises. The frontal lessons are aimed at improving students' knowledge and understanding through the presentation of theories, models and methods; students are invited to participate in the lesson with autonomy of judgement, by asking questions and presenting examples. The exercises are aimed at understanding the algorithms and models presented.

Oral exam. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student must demonstrate adequate knowledge and understanding of the issues presented or indicated, applying in a relevant manner the theories and conceptual models covered by the study programme.

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Introduction. Map-Reduce. Mining data streams. Frequent Items.  Frequent Itemsets and association rules. Mining similar items and Locality-Sensitive Hashing. Graph analysis. Link analysis and PageRank. Clustering. Recommendation systems. Mining Social-Network Graphs.  Dimensionality reduction.  Classification.

Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Freely availableonline: http://www.mmds.org

Data Mining and Analysis

M. J. Zaki and W. Meira

Freely available online: http://dataminingbook.info

Calculus I and II, Probability Theory. Programming skills and working knowledge of the C programming language.

The course provides a modern introduction to design, analysis and implementation of sequential and parallel algorithms. In particular, the course is based on a pragmatic approach to parallel programming of message-passing algorithms through the C language and the MPI library.

Knowledge and understanding. Students must have a solid background with a broad spectrum of basic knowledge of sequential and parallel algorithms:

· the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;

· they must have a solid knowledge of the design and implementation of sequential and parallel efficient algorithms;

· they must have the tools for analysing the resources used by algorithms;

· they must have a catalogue of the most well-known and efficient sequential and parallel algorithms for basic computational problems.

Applying knowledge and understanding. After the course the student should be able to:

· Describe and use the main design techniques for sequential algorithms;

· Design, prove the correctness and analyze the computational complexity of sequential algorithms;

· Understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;

· Describe and use basic sequential algorithms;

· Describe and use basic data structures; know about the existence of advanced data structures;

· Understand the difference between sequential and parallel algorithms;

· Design, implement and analyze message-passing based parallel algorithms in C using the MPI library;

· Describe and use basic parallel algorithms.

Making judgements. Students are guided to learn critically everything that is explained to them in class, to compare different approaches to solving algorithmic problems, and to identify and propose, in an autonomous way, the most efficient solution they find.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. The course promotes the development of the following skills of the student: ability to expose in precise and formal terms an abstract model of concrete problems, identifying the salient features of them and discarding the nonessential ones; ability to describe and analyze an efficient solution to the problem in question.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to enable students to abstract formal algorithmic models and problems from concrete computational problems, and to design efficient algorithmic solutions for them. This will be done using the following teaching method. Every computational problem will be introduced, motivating it with concrete examples. The presentation of each topic will be divided into four parts: 1. Description of the actual computational problem. 2. Modelling the real problem by means of an abstract problem. 3. Resolution of the abstract problem through an algorithm obtained through the application of the general techniques of design of algorithms introduced in the course. 4. Analysis of the resources used by the algorithm. The course consists of frontal lessons using slides made available to students via the Moodle platform, and classroom exercises. There will be theoretical lessons aimed at learning the basic techniques for the project and analysis of algorithms, and a part of lessons of an exercise type in which you will illustrate, with plenty of examples, how the theoretical knowledge acquired can be used in order to solve algorithmic problems of practical interest and implement parallel algorithms in C language through the MPI library.

Oral exam. Optionally, a student may be assigned a small project. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student may also be asked to design a very simple algorithm in order to assess his/her ability to identify and use the relevant design techniques; alternatively, the student may be asked to analyze the complexity of a small code fragment.

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer.  Divide and conquer. Recurrences.  Randomized algorithms.  Transform and conquer.  Dynamic programming.  Greedy algorithms. Complexity and computability. NP-Completeness. 

Parallel Algorithms

Introduction. The transition from sequential to parallel computing. Parallel complexity.  Parallel architectures.  Parallel algorithm design.  Message-Passing programming.  Sieve of Erathostenes.  Floyd all-pairs shortest path algorithm. Performance analysis.  Matrix-vector multiplication. Document classification.  Matrix multiplication.

Introduction to Algorithms. Third edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP International Edition (2004) Michael J. Quinn McGraw-Hill

Calculus. Probability and Statistics. Linear Algebra. Programming skills.

The course provides a modern introduction to data mining, which spans techniques, algorithms and methodologies for discovering structure, patterns and relationships in data sets (typically, large ones) and making predictions. Applications of data mining are already happening all around us, and, when they are done well, sometimes they even go unnoticed. For instance, how does the Google web search work? How does Shazam recognize a song? How does Netflix recommend movies to its users? The principles of data mining provide answers to these and others questions. Data mining overlaps the fields of computer science, statistical machine learning and data bases. The course aims at providing the students with the knowldedge required to explore, analyze and leverage available data in order to turn the data into valuable and actionable information for a company, for instance, in order to facilitate a decision-making process.

Knowledge and understanding. The course describes methods and models for the analysis of large amounts of data. Students must have a solid background with a broad spectrum of basic knowledge related to data mining:

• the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;
• they must have solid knowledge of data mining models and methodologies;
• they must be able to work on large data collections, including heterogeneous and produced at high speed data, in order to integrate them - in particular by knowing how to manage their origin and quality - and to carry out in-depth thematic analyses, drawing on this knowledge to improve the decision-making process.

Applying knowledge and understanding. After the course the student should be able to:

• describe and use the main data mining techniques;
• understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;
• tackle new data mining problems by selecting the appropriate methods and justifying his/her choices;
• tackle new data mining problems by designing suitable algorithms and evaluating the results;
• explain experimental results to people outside of statistical machine learning or computer science.

Making judgements. Students must have the ability to process complex and/or fragmentary data and must arrive at original and autonomous ideas and judgments, and consistent choices in the context of their work, which are particularly delicate in the profession of data scientist. The course promotes the development of independent judgment in the appropriate choice of technique/model for data processing and the critical ability to interpret the goodness of the results of the models/methods applied to the datasets under examination.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. Students should be able to organize effective dissemination and study material through the most common presentation tools, including computer-based ones, to communicate the results of data analysis processes, for example by using visualization and reporting tools aimed at different types of audiences.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to provide students with advanced tools for data analysis, through which to extrapolate relevant information from large datasets and guide the related decision-making processes. The course consists of frontal lessons using slides made available to students via the Moodle platform, and classroom exercises. The frontal lessons are aimed at improving students' knowledge and understanding through the presentation of theories, models and methods; students are invited to participate in the lesson with autonomy of judgement, by asking questions and presenting examples. The exercises are aimed at understanding the algorithms and models presented.

Oral exam. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student must demonstrate adequate knowledge and understanding of the issues presented or indicated, applying in a relevant manner the theories and conceptual models covered by the study programme.

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Introduction. Map-Reduce. Mining data streams. Frequent Items.  Frequent Itemsets and association rules. Mining similar items and Locality-Sensitive Hashing. Graph analysis. Link analysis and PageRank. Clustering. Recommendation systems. Mining Social-Network Graphs.  Dimensionality reduction.  Classification.

Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Freely availableonline: http://www.mmds.org

Data Mining and Analysis

M. J. Zaki and W. Meira

Freely available online: http://dataminingbook.info

Nessuno

Il corso fornisce da una parte una moderna introduzione alla programmazione orientata agli oggetti, in particolare al linguaggio di programmazione Java, dall’altra introduce i concetti fondamentali delle basi di dati.

Conoscenze e comprensione. I risultati attesi di apprendimento prevedono che al termine del corso gli studenti:

· conoscano e siano in grado di applicare la sintassi e la semantica caratterizzanti il linguaggio di programmazione Java;

· conoscano e siano in grado di applicare gli elementi distintivi della programmazione orientata agli oggetti;

· conoscano i principi fondamentali delle basi di dati;

· conoscano il modello Entità-Relazioni ed il design di basi di dati;

· conoscano il linguaggio SQL;

· abbiano acquisito la capacità di problem solving;

· siano in grado di sviluppare, compilare, eseguire ed effettuare il debug di applicazioni Java, incluse applicazioni per l’accesso ad una base di dati.

Capacità di applicare conoscenze e comprensione. Dopo aver seguito il corso, lo studente dovrebbe essere in grado di:

· descrivere una possibile soluzione algoritmica per un problema reale;

· effettuare il design di una base di dati;

· interrogare una base di dati;

· implementare in linguaggio Java un’applicazione.

Autonomia di giudizio. Gli studenti devono possedere la capacità di problem solving e devono pervenire a idee e giudizi originali e autonomi, a scelte coerenti nell’ambito del loro lavoro, particolarmente delicate nell’ambito della implementazione di una applicazione in un linguaggio orientato agli oggetti.Il corso promuovelo sviluppo dell’autonomia di giudizio nella scelta appropriata della soluzione migliore relativa a semplici problemi e la capacità critica di interpretare la bontà dei risultati ottenuti.

Abilità comunicative. È fondamentale che gli studenti siano in grado di comunicare con un pubblico vario e composito, non omogeneo culturalmente, in modo chiaro, logico ed efficace, utilizzando gli strumenti metodologici acquisiti e le loro conoscenze scientifiche e, in particolar modo, il lessico di specialità.
Il corso favorisce lo sviluppo delle abilità inerenti le capacità di esporre in termini precisi e formali snippets di codice sorgente in linguaggio Java, modelli Entità-Relazioni, database designs, queries SQL e la descrizione di possibili soluzioni algoritmiche a problemi reali.

Capacità di apprendimento. Gli studenti devono acquisire la capacità critica di rapportarsi, con originalità e autonomia, alle problematiche tipiche della programmazione orientata agli oggetti. Devono essere in grado di rielaborare e di applicare autonomamente le conoscenze nella più ampia prospettiva di auto-aggiornamento culturale e professionale dell'apprendimento permanente. In particolare, devono poter riusare le conoscenze acquisite nell’ambito dell’apprendimento di altri linguaggi di programmazione orientati agli oggetti e, più in generale, nell’ambito dell’Ingegneria del Software. Devono inoltre essere in grado di riusare le conoscenze legate alle basi di dati indipendentemente dallo specifico DBMS utilizzato.

Il corso si articola in lezioni frontali che si avvalgono dell’uso di slides rese disponibili agli studenti mediante la piattaforma Moodle, ed esercitazioni in aula. Le lezioni frontali sono finalizzate al miglioramento delle conoscenze e capacità di comprensione degli studenti mediante l’esposizione del linguaggio di programmazione Java, dei principi di progettazione orientata agli oggetti e dei principi relativi alle basi di dati; gli studenti sono invitati a partecipare alla lezione con autonomia di giudizio, formulando domande, presentando esempi e discutendo possibili soluzioni alternative. Le esercitazioni sono finalizzate sia alla comprensione degli algoritmi e dei codici Java presentati, ed allo sviluppo della capacità di problem solving (dato un problema, lo studente deve analizzarlo ed individuare una soluzione algoritmica appropriata, implementandola correttamente in Java), sia alla comprensione delle queries SQL, dei modelli Entità-Relazioni e dei database designs presentati.

L’esame consiste in una prova scritta,nella quale lo studente dovràdimostrare di aver acquisito da una parte la capacità di modellare ed interrogare una base di dati, dall’altra la capacità di problem solving medianteimplementazionein linguaggio Java di un algoritmorisolutivo di un problema, utilizzandocorrettamente le principali strutture dati e glialgoritmidi base visti a lezione.

Svolgimento prova scritta mediante Microsoft Teams

degli appelli di

Elementi di Informatica

Per la verifica dell’identità dello studente e la sorveglianza della prova si usa Microsoft Teams; il docente selezionerà ogni singolo studente chiedendogli di mostrare il documento di identificazione. L’esame si svolge all’interno di un team a cui gli studenti accedono mediante iscrizione da parte del docente o tramite un link che sarà comunicato via mail. Gli studenti sono invitati ad accedere al team almeno 15 minuti prima dell’orario di inizio previsto, al fine di effettuare il riconoscimento. Ogni studente parteciperà al meeting mediante un dispositivo dotato di microfono e webcam che dovrà rimanere accesa per tutta la durata della prova, inquadrando lo studente ed il foglio su cui scrive. Il docente controllerà la regolarità del lavoro degli studenti, annullando immediatamente la prova in caso di irregolarità di ogni genere.

Per la distribuzione agli studenti della traccia d’esame, il docente condivide nella chat di TEAMS un file pdf. La traccia è suddivisa in 2 esercizi, ed il docente rilascia agli studenti ognuno degli esercizi che la compongono ad intervalli di tempo determinati. La prova si svolge quindi come segue:

1. Il docente rilascia il primo esercizio all’inizio dell’appello;
   1. gli studenti stampano il testo dell’esercizio ed iniziano la stesura dell’elaborato su un foglio ben visibile dal dispositivo di acquisizione video;
   2. il docente fornisce la sua stima x del tempo sufficiente per rispondere;
   3. consegna dello svolgimento relativo al primo esercizio trascorso il tempo x;
   4. Il docente attende 2 minuti per la consegna;
2. Il docente rilascia il secondo esercizio;
   1. gli studenti stampano il testo dell’esercizio ed iniziano la stesura dell’elaborato su un foglio ben visibile dal dispositivo di acquisizione video;
   2. il docente fornisce la sua stima y del tempo sufficiente per rispondere;
   3. consegna dello svolgimento relativo al secondo esercizio trascorso il tempo y;
   4. Il docente attende 2 minuti per la consegna;
3. Il docente comunica agli studenti partecipanti la chiusura dell’appello.

Per la consegna degli elaborati relativi ai singoli esercizi, si richiede che lo studente fotografi i fogli relativi, includendo anche un’immagine del libretto universitario o, in alternativa, un documento di riconoscimento. Le foto dovranno essere inserite in una directory chiamata “Esercizio_a_b_c_d” in cui:

• a indica il numero progressivo dell’esercizio (1, 2 o 3);
• b è EI (per Elementi di Informatica)
• c indica il nome dello studente;
• d indica il cognome dello studente.

La directory deve quindi essere compressa, ad esempio in formato zip, ed il file risultante deve essere consegnato tramite la chat del team.

Non è possibile consegnare lo svolgimento di un esercizio prima del tempo stabilito e passare allo svolgimento dell’esercizio successivo. Lo studente che intende rinunciare alla prova può darne comunicazione al docente in qualunque momento, ed uscire immediatamente dopo dal team. Non è possibile allontanarsi per nessun motivo durante lo svolgimento della prova. Lo studente è tenuto ad assicurarsi di disporre di tutto quanto il necessario allo svolgimento (microfono, webcam, stampante, fotocamera, penna, numero di fogli adeguato).

Orario di ricevimento

Previo appuntamento da concordare via email o al termine delle lezioni.

Introduzione al corso. Computers, Internet e Java. ApplicazioniJava. Input/Output ed operatori.Classi, oggetti, metodi e stringhe.Strutture di controllo. Operatori di assegnamento, incremento e decremento. Operatori logici. Dettagli sui metodi. Array ed ArrayList. Dettagli su classi e oggetti. Ereditarietà. Polimorfismo. Interfacce. Dettagli sulla gestione delle eccezioni. Stringhe, caratteri ed espressioni regolari. Files, Input/Output Streams, NIO e serializzazione XML. Generic collections. Espressioni lambda e streams. Ricorsione. Algoritmi di ricerca ed ordinamento, notazione asintotica. Concorrenza. Basi di dati ed utenti. Concetti ed architettura dei DBMS (Database Management Systems). Modellazione dei dati mediante il modello Entità-Relazioni (ER). Il modello relazionale, schemi e vincoli. Il linguaggio SQL. Accesso ai database con JDBC.

Java How to Program, Early Objects, 11th Edition

Deitel & Deitel

Pearson

Fundamentals Of Database Systems, Seventh Edition

Elmasri, Navathe

Pearson

Calculus I and II, Probability Theory. Programming skills and working knowledge of the C programming language.

The course provides a modern introduction to design, analysis and implementation of sequential and parallel algorithms. In particular, the course is based on a pragmatic approach to parallel programming of message-passing algorithms through the C language and the MPI library.

Knowledge and understanding. Students must have a solid background with a broad spectrum of basic knowledge of sequential and parallel algorithms:

· the students must have the basic cognitive tools to think analytically, creatively, critically and in an inquiring way, and have the abstraction and problem-solving skills needed to cope with complex systems;

· they must have a solid knowledge of the design and implementation of sequential and parallel efficient algorithms;

· they must have the tools for analysing the resources used by algorithms;

· they must have a catalogue of the most well-known and efficient sequential and parallel algorithms for basic computational problems.

Applying knowledge and understanding. After the course the student should be able to:

· Describe and use the main design techniques for sequential algorithms;

· Design, prove the correctness and analyze the computational complexity of sequential algorithms;

· Understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;

· Describe and use basic sequential algorithms;

· Describe and use basic data structures; know about the existence of advanced data structures;

· Understand the difference between sequential and parallel algorithms;

· Design, implement and analyze message-passing based parallel algorithms in C using the MPI library;

· Describe and use basic parallel algorithms.

Making judgements. Students are guided to learn critically everything that is explained to them in class, to compare different approaches to solving algorithmic problems, and to identify and propose, in an autonomous way, the most efficient solution they find.

Communication. It is essential that students are able to communicate with a varied and composite audience, not culturally homogeneous, in a clear, logical and effective way, using the methodological tools acquired and their scientific knowledge and, in particular, the specialty vocabulary. The course promotes the development of the following skills of the student: ability to expose in precise and formal terms an abstract model of concrete problems, identifying the salient features of them and discarding the nonessential ones; ability to describe and analyze an efficient solution to the problem in question.

Learning skills. Students must acquire the critical ability to relate, with originality and autonomy, to the typical problems of data mining and, in general, cultural issues related to other similar areas. They should be able to develop and apply independently the knowledge and methods learnt with a view to possible continuation of studies at higher (doctoral) level or in the broader perspective of cultural and professional self-improvement of lifelong learning. Therefore, students should be able to switch to exhibition forms other than the source texts in order to memorize, summarize for themselves and for others, and disseminate scientific knowledge.

The course aims to enable students to abstract formal algorithmic models and problems from concrete computational problems, and to design efficient algorithmic solutions for them. This will be done using the following teaching method. Every computational problem will be introduced, motivating it with concrete examples. The presentation of each topic will be divided into four parts: 1. Description of the actual computational problem. 2. Modelling the real problem by means of an abstract problem. 3. Resolution of the abstract problem through an algorithm obtained through the application of the general techniques of design of algorithms introduced in the course. 4. Analysis of the resources used by the algorithm. The course consists of frontal lessons using slides made available to students via the Moodle platform, and classroom exercises. There will be theoretical lessons aimed at learning the basic techniques for the project and analysis of algorithms, and a part of lessons of an exercise type in which you will illustrate, with plenty of examples, how the theoretical knowledge acquired can be used in order to solve algorithmic problems of practical interest and implement parallel algorithms in C language through the MPI library.

Oral exam. Optionally, a student may be assigned a small project. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student may also be asked to design a very simple algorithm in order to assess his/her ability to identify and use the relevant design techniques; alternatively, the student may be asked to analyze the complexity of a small code fragment.

Office Hours

By appointment; contact the instructor by email or at the end of class meetings.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer.  Divide and conquer. Recurrences.  Randomized algorithms.  Transform and conquer.  Dynamic programming.  Greedy algorithms. Complexity and computability. NP-Completeness. 

Parallel Algorithms

Introduction. The transition from sequential to parallel computing. Parallel complexity.  Parallel architectures.  Parallel algorithm design.  Message-Passing programming.  Sieve of Erathostenes.  Floyd all-pairs shortest path algorithm. Performance analysis.  Matrix-vector multiplication. Document classification.  Matrix multiplication.

Introduction to Algorithms. Third edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP International Edition (2004) Michael J. Quinn McGraw-Hill

Analisi Matematica. Probabilità e statistica. Algebra lineare. Programmazione ed analisi di algoritmi.

Introduzione al corso. Map-Reduce. (2 ore) Mining data streams. Frequent Items. (6 ore)  Frequent Itemsets ed association rules.(4 ore)  Mining similar items e Locality-Sensitive Hashing. (2 ore)  Analisi di grafi. Link analysis e PageRank. (2 ore)  Clustering. (4 ore)  Recommendation systems. (4 ore)  Mining Social-Network Graphs. (4 ore)  Dimensionality reduction. (2 ore)  Classification. (6 ore) Esercitazioni. (6 ore).

Il corso fornisce una moderna introduzione al data mining, un insieme di tecniche, algoritmi e metodologie per scoprire la struttura, patterns e relazioni in insiemi di dati (tipicamente, quelli più grandi) e fare previsioni. Le applicazioni del data mining stanno già accadendo intorno a noi, e se ben fatte, possono a volte anche passare inosservate. Come funziona la ricerca sul web di Google? Come fa Shazam a riconoscere una canzone? Come fa Netflix a raccomandare film a ciascuno dei suoi utenti? I principi del data mining forniscono le risposte di base a queste e ad altre domande simili. Il data mining abbraccia i campi dell’informatica, dello statistical machine learning e dei database. Obiettivo del corso è mettere in grado gli studenti di esplorare, analizzare e sfruttare i dati disponibili al fine di trasformarli in informazioni quantitative e qualitative di valore ed interesse per una azienda, ad esempio ai fini di un processo di decision-making.

Risultati di apprendimento

Dopo aver seguito il corso, lo studente dovrebbe essere in grado di:

•        descrivere ed utilizzare le principali tecniche di data mining;

•        comprendere le differenze tra algoritmi diversi che risolvono uno stesso problema e riconoscere quale algoritmo è il migliore rispetto a condizioni diverse;

•        affrontare nuovi problemi di data mining scegliendo i metodi più appropriati e giustificando le proprie scelte;

•        affrontare nuovi problemi di data mining progettando appositi algoritmi e valutando i risultati;

•        spiegare i risultati ottenuti sperimentalmente anche a persone con un background teorico diverso da statistica e/o informatica.

L’esame è orale. Durante l’esame, allo studente viene chiesto di illustrare argomenti teorici per verificare la sua conoscenza e comprensione degli argomenti scelti. 

Mining of Massive Datasets 

J. Leskovec, A. Rajaraman and J. Ullman

Disponibile gratuitamente online: http://www.mmds.org

Data Mining and Analysis

M. J. Zaki and W. Meira

Disponibile gratuitamente online: http://dataminingbook.info

Analisi I e II, Teoria della Probabilita’. Conoscenze pregresse del linguaggio di programmazione C.

Algoritmi sequenziali

Introduzione. Ordini di grandezza. Analisi di algoritmi. Decrease and conquer. Divide and conquer. Ricorrenze. (7 ore) Algoritmi randomizzati. (5 ore)  Transform and conquer. (2 ore)  Lower bound for sorting. Linear time sorting algorithms: Counting sort, Radix sort and Bucket sort. (3 ore) Order statistics. Selection in expected and worst case linear time. (2 ore) Programmazione dinamica. (4 ore) Algoritmi greedy. (3 ore) Complessita’ e calcolabilita’. NP-Completezza. (7 ore)

Algoritmi paralleli

1) Introduzione. Metodo scientifico moderno. Concorrenza e parallelismo. Equazioni di Bernstein. Evoluzione del supercalcolo. Calcolatori paralleli. Grafo delle dipendenze dei dati. Data parallelism. Functional Parallelism. Pipelining. Approcci per la programmazione di calcolatori paralleli. (2 ore)

2) Architetture parallele. Reti di interconnessione. Shared e switched media. Topologie di rete. 2D mesh. Binary tree. Hypertree. Fat tree. Butterfly. Ipercubo. Torus. Shuffle-exchange. Processor arrays. Multiprocessori centralizzati e distribuiti. Multicomputers asimmetrici e simmetrici. Clusters e reti di workstations. Tassonomia di Flinn. (5 ore)

3) Parallel algorithm design. Modello task-channel. Metodologia PCAM di Foster. Decomposizioni, tasks e grafo delle dipendenze dei tasks. Grain size di una decomposizione. Grado di concorrenza. Critical path length. Grafo delle interazioni dei tasks. Processi e mapping. Recursive decomposition, Data decomposition Exploratory decomposition, Speculative decomposition. Decomposizione di dati di input, intermedi e di output. Decomposizione ibride e gerarchiche. The Owner Computes Rule. Tasks static e dinamici. Comunicazione locale, globale, strutturata e non strutturata. Task interactions: read-only, read-write, one-way, two-way. Comunicazione static e dinamica, sincrona ed asincrona. Algoritmi red-black.  Divide and conquer. Agglomerazione. Effetto surface to volume. Communication/computation ratio. Replicare la computazione per eliminare comunicazioni. Mapping. NP-completeness del mapping. Mapping static e dinamico.     Mappings based on data partitioning. Mappings based on task graph partitioning. Hybrid mappings. Probabilistic mapping, cyclic and block-cyclic. Graph partitioning. Recursive bisection. Quad and Oct-trees. Space-filling curves. Scattered decomposition. Dynamic load-balancing. Centralized dynamic mapping, master-slave (manager-worker), chunck scheduling. Distributed dynamic mapping. Dynamic data driven mapping. Dynamic geometric decomposition: Adaptive Mesh Refinement (AMR). Esempi di progettazione di algoritmi paralleli: boundary value problem, reductions, n-body problem. Data input. (10 ore)

4) Message-Passing programming. Message-passing model. MPI. Circuit-SAT problem. Communicators. Point-to-point communications: vari tipi di send e receive. Collective communications: broadcast, reductions, scatter, gather, all-gather,  all-to-all. Benchmark. (2 ore)

5) Crivello di Eratostene: progettazione, analisi, implementazione e benchmark. (2 ore)

6) Algoritmo di Floyd all-pairs shortest path: progettazione, analisi, implementazione e benchmark. (2 ore)

7) Performance analysis. Tempo di esecuzione sequenziale e parallelo. Communication overhead. Overhead totale. Speedup ed efficienza. Speedup relativo, reale, assoluto, relae asintotico e relativo asintotico. Cost-normalized speedup. Numero ottimale di processori. Speedup superlineare. Legge di Amdahl-Ware. Legge di  Gustafson-Barsis. Metrica di Karp-Flatt. Legge di Lee (generalizzazione della legge di Amdahl-Ware). Metrica di isoefficienza (Grama, Gupta and Kumar). Funzione di scalabilita’ di Sun e Ni. Cost-optimality (work-efficiency). Cost-optimality ed isoefficienza. Grado di concorrenza ed isoefficienza. Impatto della non cost-optimality di un algoritmo parallelo. Minimum Parallel execution Time. Minimum Cost-Optimal Parallel Execution Time. (7 ore)

8) Moltiplicazione matrice-vettore. Algoritmo sequenziale. Rowwise block-striped decomposition. Columnwise block-striped decomposition. Checkerboard block decomposition. implementazione e benchmark. (3 ore)

9) Classificazione di documenti. Design. Manager-worker paradigm. Comunicazioni nonblocking. (2 ore)

10) Moltiplicazione di matrici. Algoritmo sequenziale iterativo row-oriented e ricorsivo block-oriented.  Rowwise block-striped  parallel algorithm. Algoritmo di Cannon. Algoritmo di Fox. Algoritmo DNS (dei tre indiani). (3 ore)

Esercitazioni. (21 ore)

Il corso fornisce una moderna introduzione alla progettazione, analisi ed implementazione di algoritmi sequenziali e paralleli. In particolare, il corso e’ basato su un approccio pratico alla programmazione parallela di algoritmi message-passing in linguaggio C con la libreria MPI.

Dopo aver seguito il corso, lo studente dovrebbe essere in grado di:

1)      descrivere ed utilizzare le principali tecniche di progettazione di algoritmi sequenziali;

2)      progettare, provare la correttezza, implementare ed analizzare la complessita’ computazionale di algoritmi sequenziali;

3)      comprendere le differenze tra algoritmi diversi che risolvono uno stesso problema e riconoscere quale algoritmo e’ il migliore rispetto a condizioni diverse;

4)      descrivere ed utilizzare algoritmi sequenziali di base;

5)      descrivere ed utilizzare strutture dati di base; conoscere l’esistenza di strutture dati avanzate;

6)      comprendere le differenze tra algoritmi sequenziali e paralleli;

7)      progettare, provare la correttezza, implementare ed analizzare la complessita’ computazionale di algoritmi paralleli basati su message-passing in C  utilizzando la libreria MPI;

8)      descrivere ed utilizzare algoritmi paralleli di base.

L’esame e’ orale. Opzionalmente, allo studente puo’ essere assegnato un piccolo progetto. Duramte l’esame, allo studente viene chiesto di illustrare argomenti teorici per verificare la sua conoscenza e comprensione degli argomenti scelti. Allo studente puo’ essere chiesto di progettare un semplice algoritmo per verificare la sua capacita’ di identificare ed utilizzare le tecniche di progettazione piu’ appropriate. Alternativamente, allo studente puo’ essere chiesto di analizzare la complessita’ computazionale di un breve frammento di codice.