Diario delle lezioni (Ingegneria degli Algoritmi, A.A. 2011-2012)

Wednesday, March 7th - Introduction and overview. Administrivia. Slides: course overview

Friday, March 9th - Microscopic and macroscopic operations: from nanoseconds to seconds. External memory model (Aggarwal & Vitter): N, M, and B. Fundamental external memory bounds: scanning, sorting, searching. Data permutation: I/O-analysis of the naive linear-time algorithm, scan&sort algorithm. Back of the envelope calculations for external memory: how long does it take to sort 1TB of data?

• The back of the envelope (Column 7 of Programming Pearls, by Jon Bentley). On-line version. Interesting and funny reading: highly recommended!

Wednesday, March 14th - Spatial and temporal locality, reuse distance. Matrix multiplication. I/O analysis of the naive algorithm. Blocking: a technique to improve temporal locality. Getting rid of the tall cache assumption (M ≥ B²): Vitter and Shriver's recursive algorithm.

• C. Demetrescu and I. Finocchi: notes on blocked matrix multiplication, 2011.
• J. S. Vitter and E. A. M. Shriver: Algorithms for Parallel Memory I: Two-Level Memories, appeared in Algorithmica, 1994. Only Section 7 (matrix multiplication), pages 144-145. In the analysis, assume P=1 (we considered only the case with one single disk, instead of P parallel disks).

Friday, March 16th - External memory sorting. 2-way mergesort: I/O analysis, recursive and iterative implementation, discussion of its key inefficiency. Multiway mergesort: analysis of the number of I/Os and of the running time (using a priority queue for minimum extraction). Can we do more than one pass? Another back of the envelope calculation.

• K. Mehlhorn, P. Sanders. Algorithms and data structures: The basic toolbox, 2009, Chapter 5 (Sorting and selection), Section 7. On-line version.

Wednesday, March 21st - giornata Shenker-D'Ambrosio, didattica sospesa come da delibera CAD

Friday, March 23rd - Hands on external memory algorithms. Experiment 1: which B should we use? Goal: maximizing disk throughput. Experiment 2: matrix multiplication. Evaluating the effect of I/Os in computationally intensive computations.

• make-rand-file.c: utility for creating large files
• rand-file-scan.c: random file scan (experiment 1)
• iterative-matmul.c: blocked matrix multiplication (experiment 2)
• gnuplot_sources.tar.gz: gnuplot sources related to experiment 1
• rand_file_scan_results.tar.gz: charts (produced by gnuplot) obtained from experiment 1
• gnuplot home page: command-line driven graphing utility for Linux and many other operating systems

Wednesday, March 28th - Proving lower bounds via adversary-based arguments. Two examples: 20-questions game, comparison-based sorting. Lower bound on the number of I/Os required by external memory comparison-based sorting algorithms.

• Sally A. Goldman and Kenneth J. Goldman: an introduction to adversary-based lower bounds.
• Gerth Stølting Brodal and Rolf Fagerberg: sorting upper and lower bounds (slides).

Friday, March 30th - Balanced search trees by split and fuse. (2,3)-trees: implementation and analysis. Searching in external memory: B-trees.

• Demetrescu, Finocchi, Italiano. Algoritmi e strutture dati, paragrafi 6.4 e 6.5.

Wednesday, April 4th - Introduction to cache-friendly algorithms. Recap on memory hierarchy. How do caches work? Sets, lines, blocks. Fundamental cache parameters. Impact of associativity: conflict misses (an example on direct-mapped caches). Cache performance metrics.

• R. Bryant, D. O'Hallaron. Computer systems: a programmer's perspective. Chapter 6.
• Slides on memory hierarchies: part 1

Wednesday, April 11th - The memory mountain: effect of different strides (spatial locality) and different working set sizes (temporal locality). Writing cache-friendly code: miss rate analysis for matrix multiplication with permuted loops. Programming difficulties posed by hierarchical memories. Towards a theoretical model: introduction to cache-obliviousness. Ideal cache and justification.

• R. Bryant, D. O'Hallaron. Computer systems: a programmer's perspective. Chapter 6.
• Slides on memory hierarchies: part 2
• Slides on cache-oblivious algorithms: introduction to the ideal cache model

Wednesday, April 18th - First cache oblivious algorithms and analyses. A trivial example: array scan. Deterministic selection: the median-of-5 algorithm by Blum, Floyd, Pratt, Rivest and Tarjan. Cache miss analysis: a failed attempt, a successful attempt using a stronger base case. Formal analysis and intuition on the recursion tree.

• Demetrescu, Finocchi, Italiano: randomized and deterministic selection
• Lecture notes by Erik Demaine: Cache-oblivious algorithms and data structures
• Video lectures from MIT's Introduction to Algorithms course on cache-oblivious algorithms (with transcripts): lecture 24, lecture 25.

Friday, April 20th - Binary search: stronger base case doesn't help here. Van Emde Boas recursive layout. Cache-oblivious matrix multiplication (row-major and Z-order layouts).

• Lecture notes by Erik Demaine linked above
• Original cache-oblivious paper by Frigo, Leiserson, Prokop, and Ramachandran, appeared in IEEE Symposium on Foundations of Computer Science, FOCS'99. The matrix multiplication algorithm described in class only applies to square matrices, and the analysis is simpler than the one contained in the paper.

Tuesday, April 24th - Prova intermedia

Wednesday, May 2nd - Lezione annullata causa missione del docente

Friday, May 4th - Didattica sospesa per 27° IT Meeting (incontro con le aziende)

Wednesday, May 9th - MapReduce: introduction

Friday, May 11th - Computational models and algorithm design in MapReduce

• Slides on MapReduce (by Luigi Laura)
• Apache Hadoop web site
• A useful Hadoop tutorial

Wednesday, May 16th - Data streaming: applications, computational model, three puzzles (missing number, fishing, pointer and chaser).

• I. Finocchi: slides on algorithmics for data streams
• M. Muthukrishnan: survey on data streams: algorithms and applications

Friday, May 18th - Sampling infinite streams: reservoir sampling (algorithm and analysis). Approximating the solution (parameter epsilon) and probabilistic guarantees (parameter delta). The frequent items problem: definitions, sticky sampling algorithm (without analysis).

• C. Demetrescu and I. Finocchi: survey on algorithms for data streams, Handbook of Applied Algorithms: Solving Scientific, Engineering and Practical Problems, 2008.
• The Britney Spears problem: tracking who's hot and who's not presents an algorithmic challenge, by Brian Hayes. A popular paper on stream algorithmics appeared in volume 96 of the American Scientist, 2008.
• Slides linked above

Wednesday, May 23rd - Frequent items: analysis of sticky sampling. Triangle counting: a sampling-based approach.

• Original VLDB 2002 (Very Large Data Bases Conference) paper describing Sticky Sampling: Approximate Frequency Counts over Streaming Data, by G. Manku and R. Motwani.
• PODS 2006 (ACM Symposium on Principles of Database Systems) paper on triangle counting: Triangle counting in data streams, by Buriol, Frahling, Leonardi, Marchetti-Spaccamela, and Sohler.
• Survey and slides (linked above)

Friday, May 25th - Sketches. Approximating the number of distinct elements via probabilistic counting: FM-sketch. Definition of frequency moments.

• Survey and slides (linked above)

Wednesday, May 30th - Graph matching. Proving lower via communication complexity reductions.

Friday, June 1st - Amdahl's law. Performance profiling.

-- IreneFinocchi - 18 Mar 2013