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

Wednesday, February 27th - Introduction and overview. Administrivia. Slides: course overview

Monday, March 4th - Algorithms for data streams. Motivations, applications, and theoretical model. Streaming puzzles: 1) missing number 2) curious George goes fishing

Wednesday, March 6th - Puzzle 3: pointer and chaser. Sampling infinite streams: reservoir sampling (algorithm and analysis).

Monday, March 11th - The frequent items problem. Problem definition: frequency threshold, approximating the solution (parameter epsilon) and probabilistic guarantees (parameter delta). Sticky sampling algorithm (algorithm and analysis).

Wednesday, March 13th - Sketches. Approximating the number of distinct elements via probabilistic counting: FM-sketch (probabilistic counting). Analysis: an intuition.

  • Survey and slides (linked above)

Monday, March 18th - Rigorous analysis of probabilistic counting. Generalization of distinct items: frequency moments (only definition).

  • Survey [S3] and slides [S1] linked above

Wednesday, March 20th - Triangle counting (arbitrary streams).

  • 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 [S3] and slides [S1] linked above

Wednesday, March 27th - Proving lower bounds via communication complexity reductions: an example related to triangle counting. Homework discussion.

  • Slides [S1] linked above

Wednesday, April 3rd - Microscopic and macroscopic operations: from nanoseconds to seconds. External memory model (Aggarwal & Vitter): N, M, and B. Fundamental external memory bounds: scanning and sorting. Data permutation: I/O-analysis of the naive linear-time algorithm, scan&sort algorithm. External memory sorting. 2-way mergesort: I/O analysis, recursive and iterative implementation, discussion of its key inefficiency.

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

Monday, April 8th - k-way mergesort. I/O analysis. Efficient implementation based on priority queues. Can we do more than one pass? A back of the envelope calculation.

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

Wednesday, April 10th - Spatial and temporal locality, reuse distance. Matrix multiplication. I/O analysis of the naive algorithm. Blocking: a technique to improve temporal locality.

Monday, April 15th - prova intermedia

Wednesday, April 24th (4 hours lesson) - Getting rid of the tall cache assumption (M ≥ B2): Vitter and Shriver's recursive algorithm. 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.

Monday, May 6th - 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).

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

Wednesday, May 8th - Cache performance metrics. 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.

Monday, May 13th - 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.

Wednesday, May 15th - Binary search: stronger base case doesn't help here. Van Emde Boas recursive layout. Cache-oblivious matrix multiplication (row-major layout).

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

May 20th - May 29th - homework presentations

-- IreneFinocchi - 18 Mar 2013

Edit | Attach | Watch | Print version | History: r35 < r34 < r33 < r32 < r31 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r35 - 2013-05-29 - IreneFinocchi






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback