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.

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.

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.

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.

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.

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.

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

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

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2012-04-20 - 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-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback