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

Friday, March 18th - Introduction and overview. Administrivia

Tuesday, March 22nd - Microscopic and macroscopic operations. Back of the envelope calculations for external memory. Fundamental external memory bounds for scanning and sorting sequences. Why scan and sort? An example related to permuting.

Friday, March 25th - Matrix multiplication. Improving temporal locality through blocking. From row-major order to Z-layout: 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).

Tuesday, March 29th - 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.

• MakeRandFile.c: utility for creating large files
• rand-file-scan.c: random file scan (experiment 1)
• iterative-matmul.c: blocked matrix multiplication (experiment 2)
• gnuplot.tar.gz: charts and gnuplot sources related to experiment 1

Friday, April 1st - 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.

Tuesday, April 5th - 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).

Tuesday, April 12th - 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 13th - 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
• 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.
• Slides on cache-oblivious algorithms: introduction to the ideal cache model

Friday, April 15th - First cache oblivious algorithms and analysis. 1) Scan. 2) Deterministic selection: a failed analysis, a successful analysis using a stronger base case. 3) Binary search: stronger base case doesn't help here. Van Emde Boas recursive layout.

• Demetrescu, Finocchi, Italiano: randomized and deterministic selection
• Lecture notes by Erik Demaine (linked above)

Tuesday, April 19th - Cache-oblivious matrix multiplication. Cache-oblivious sorting: introduction to funnelsort, structure of a k-way merger. Space required by a k-way merger. Analysis of cache misses (to be completed).

• 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.

Friday, April 22nd - vacanze di Pasqua

Tuesday, April 26th - vacanze di Pasqua

Friday, April 29th - Interruzione della didattica per prove intermedie

Tuesday, May 3rd - Prova intermedia alle 10:00

Friday, May 6th - K-way merger: complete analysis of cache misses.

• FOCS'99 paper by Frigo, Leiserson, Prokop, and Ramachandran (linked above)

Tuesday, May 10th - Ore restituite al corso di Algoritmi Avanzati

Friday, May 13th - Algorithms for data streams. Motivations and model. Approximating the solution (parameter epsilon) and probabilistic guarantees (parameter delta). The frequent items problem: definitions.

• 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.

Tuesday, May 17th - Sampling infinite streams: reservoir sampling (algorithm and analysis). Frequent items: sticky sampling algorithm (without analysis).

• Original VLDB 2002 paper describing Sticky Sampling: Approximate Frequency Counts over Streaming Data, by G. Manku and R. Motwani.
• On the personality of Rajeev Motwani, Stanford Report, 2009.

Tuesday, May 24th - Frequent items: analysis of sticky sampling. Definition of frequency moments. Introduction to probabilistic counting.

Friday, May 27th - Number of distinct elements: probabilistic counting.

• Survey on algorithms for data streams (linked above)

Tuesday, May 31st - Concurrent data structures: what does it mean to be correct? An example: concurrent queues.

• "The art of multiprocessor programming", Herlihy and Shavit: section 3.1 and section 3.2
• Correctness conditions and linearizability: slides (pptx)

Tuesday, June 7th - Correctness: all about linearizability. Progress conditions.

• "The art of multiprocessor programming", Herlihy and Shavit: section 3.5 and section 3.6

Tuesday, June 14th - Discussion of homeworks and exams. Q&A.

-- IreneFinocchi - 19 Mar 2011