DiarioLezioni1112 < Ing

Tags: view all tags
---++Diario delle lezioni (Ingegneria degli Algoritmi, A.A. 2011-2012)

<font color="#AF0F0F"><b>Wednesday, March 7th</b></font> - Introduction and overview. Administrivia.  Slides: [[http://twiki.di.uniroma1.it/twiki/viewfile/Ing_algo/WebHome?filename=AlgorithmEngineering_AA2011_2012.pdf][course overview]]

<font color="#AF0F0F"><b>Friday, March 9th</b></font> - 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). [[http://netlib.bell-labs.com/cm/cs/pearls/bote.html][On-line version]]. Interesting and funny reading: highly recommended!

<font color="#AF0F0F"><b>Wednesday, March 14th</b></font> - 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 &ge; B<sup>2</sup>_): Vitter and Shriver's recursive algorithm.

   * C. Demetrescu and I. Finocchi: notes on [[%ATTACHURL%/matmul.pdf][blocked matrix multiplication]], 2011.
   * J. S. Vitter and E. A. M. Shriver: [[%ATTACHURL%/ViS94.sorting_io.pdf][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).

<font color="#AF0F0F"><b>Friday, March 16th</b></font> - 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. [[http://www.mpi-inf.mpg.de/~mehlhorn/Toolbox.html][On-line version]].

<font color="#AF0F0F"><b>Wednesday, March 21st</b></font> - giornata Shenker-D'Ambrosio, didattica sospesa come da delibera CAD

<font color="#AF0F0F"><b>Friday, March 23rd</b></font> - 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.

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

<font color="#AF0F0F"><b>Wednesday, March 28th</b></font> - 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: [[%ATTACHURL%/adv-lb.pdf][an introduction to adversary-based lower bounds]].
   * Gerth Stølting Brodal and Rolf Fagerberg: [[%ATTACHURL%/sorting-2.pdf][sorting upper and lower bounds]] (slides).

<font color="#AF0F0F"><b>Friday, March 30th</b></font> - 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_, [[http://twiki.di.uniroma1.it/twiki/viewfile/Ing_algo/WebHome?filename=B_trees.pdf][paragrafi 6.4 e 6.5]].

<font color="#AF0F0F"><b>Wednesday, April 4th</b></font> - 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: [[%ATTACHURL%/memoryHierarchies_part1.pdf][part 1]]

<font color="#AF0F0F"><b>Wednesday, April 11th</b></font> - 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: [[%ATTACHURL%/memoryHierarchies_part2.pdf.gz][part 2]]
   * Slides on cache-oblivious algorithms: [[%ATTACHURL%/cacheOblivious_model_intro.pdf][introduction to the ideal cache model]]

<font color="#AF0F0F"><b>Wednesday, April 18th</b></font> - 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: [[%ATTACHURL%/selection.pdf][randomized and deterministic selection]]
   * Lecture notes by Erik Demaine: [[http://erikdemaine.org/papers/BRICS2002/][Cache-oblivious algorithms and data structures]] 
   * Video lectures from MIT's Introduction to Algorithms course on cache-oblivious algorithms (with transcripts): [[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-24-advanced-topics-cont./][lecture 24]], [[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-25-advanced-topics-cont.-discussion-of-follow-on-classes/][lecture 25]].

<font color="#AF0F0F"><b>Friday, April 20th</b></font> -  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
   * [[%ATTACHURL%/FrigoLePr99.ps.gz][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.

<font color="#AF0F0F"><b>Tuesday, April 24th</b></font> - *Prova intermedia*

<font color="#AF0F0F"><b>Wednesday, May 2nd</b></font> - Lezione annullata causa missione del docente

<font color="#AF0F0F"><b>Friday, May 4th</b></font> - Didattica sospesa per 27° IT Meeting (incontro con le aziende)

<font color="#AF0F0F"><b>Wednesday, May 9th</b></font> - !MapReduce: introduction

<font color="#AF0F0F"><b>Friday, May 11th</b></font> - Computational models and algorithm design in !MapReduce

   * [[%ATTACHURL%/slideMapReduceTalkDI.pdf][Slides on MapReduce]] (by Luigi Laura)
   * [[http://hadoop.apache.org/][Apache Hadoop]] web site
   * A useful [[http://www.michael-noll.com/tutorials/running-hadoop-on-ubuntu-linux-single-node-cluster/][Hadoop tutorial]]

<font color="#AF0F0F"><b>Wednesday, May 16th</b></font> - Data streaming: applications, computational model, three puzzles (missing number, fishing, pointer and chaser).

   * I. Finocchi: slides on [[%ATTACHURL%/streaming.pdf][algorithmics for data streams]]
   * M. Muthukrishnan: survey on [[%ATTACHURL%/muthu.pdf][data streams: algorithms and applications]]

<font color="#AF0F0F"><b>Friday, May 18th</b></font> - 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 [[%ATTACHURL%/chapter08-dataStreams.pdf][algorithms for data streams]], Handbook of Applied Algorithms: Solving Scientific, Engineering and Practical Problems, 2008.
   * [[http://www.americanscientist.org/issues/pub/the-britney-spears-problem/1][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

<font color="#AF0F0F"><b>Wednesday, May 23rd</b></font> - Frequent items: analysis of sticky sampling. Triangle counting: a sampling-based approach.

   * Original VLDB 2002 (Very Large Data Bases Conference) paper describing Sticky Sampling: [[%ATTACHURL%/02vldb-freq.pdf][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: [[%ATTACHURL%/p253-buriol.pdf][Triangle counting in data streams]], by Buriol, Frahling, Leonardi, Marchetti-Spaccamela, and Sohler.
   * Survey and slides (linked above)

<font color="#AF0F0F"><b>Friday, May 25th</b></font> - Sketches. Approximating the number of distinct elements via probabilistic counting: FM-sketch. Definition of frequency moments.

   * Survey and slides (linked above)

<font color="#AF0F0F"><b>Wednesday, May 30th</b></font> - Graph matching. Proving lower via communication complexity reductions.

<font color="#AF0F0F"><b>Friday, June 1st</b></font> - Amdahl's law. Performance profiling.


<!--

<font color="#AF0F0F"><b>Friday,  April 15th</b></font> - 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.

<font color="#AF0F0F"><b>Tuesday, April 19th</b></font> - 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).

   * [[%ATTACHURL%/FrigoLePr99.ps.gz][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.

<font color="#AF0F0F"><b>Friday, April 22nd</b></font> - vacanze di Pasqua

<font color="#AF0F0F"><b>Tuesday, April 26th</b></font> - vacanze di Pasqua

<font color="#AF0F0F"><b>Friday, April 29th</b></font> -  Interruzione della didattica per prove intermedie

<font color="#AF0F0F"><b>Tuesday, May 3rd</b></font> -  *Prova intermedia alle 10:00*

<font color="#AF0F0F"><b>Friday,  May 6th</b></font> - K-way merger: complete analysis of cache misses.

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

<font color="#AF0F0F"><b>Tuesday, May  10th</b></font> - Ore restituite al corso di Algoritmi Avanzati

<font color="#AF0F0F"><b>Friday,  May 13th</b></font> - 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 [[%ATTACHURL%/chapter08-dataStreams.pdf][algorithms for data streams]], Handbook of Applied Algorithms: Solving Scientific, Engineering and Practical Problems, 2008.
   * [[http://www.americanscientist.org/issues/pub/the-britney-spears-problem/1][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.

<font color="#AF0F0F"><b>Tuesday, May 17th</b></font> - Sampling infinite streams: reservoir sampling (algorithm and analysis). Frequent items: sticky sampling algorithm (without analysis).

   * Original VLDB 2002 paper describing Sticky Sampling: [[%ATTACHURL%/02vldb-freq.pdf][Approximate Frequency Counts over Streaming Data]], by G. Manku and R. Motwani.
   * On the personality of [[http://news.stanford.edu/news/2009/june10/rajeev_motwani-061009.html][Rajeev Motwani]], Stanford Report, 2009.

<font color="#AF0F0F"><b>Tuesday, May  24th</b></font> - Frequent items: analysis of sticky sampling. Definition of frequency moments. Introduction to probabilistic counting.

<font color="#AF0F0F"><b>Friday,  May 27th</b></font> - Sketches. Approximating the number of distinct elements via probabilistic counting: FM-sketch. Definition of frequency moments.

   * Survey on algorithms for data streams (linked above)

<font color="#AF0F0F"><b>Tuesday, May 31st</b></font> - 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: [[%ATTACHURL%/chapter_03.pptx][slides (pptx)]]

<font color="#AF0F0F"><b>Tuesday, June 7th</b></font> - Correctness: all about linearizability. Progress conditions.

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

<font color="#AF0F0F"><b>Tuesday, June 14th</b></font> - Discussion of homeworks and exams. Q&A.

-->







-- Users.IreneFinocchi - 18 Mar 2013