DM207 I/O-Efficient Algorithms and Data Structures

Fall 2009
Rolf Fagerberg

Official Course Description

See the course description at the web pages of the faculty.

Time and Place

The schedule in the 1st quarter is as follows:

• Mondays 10.15 to 12.00 in Imadas seminar room.
• Thursdays 10.15 to 12.00 in Imadas seminar room.

The schedule in the 2nd quarter is as follows:

• Mondays 12.15 to 14.00 in Imadas seminar room.
• Thursdays 12.15 to 14.00 in Imadas seminar room.

There will be a few extra hours (mainly in Week 44) to make up for the fact that the course starts was postponed. Times for theses will be emailed to participants.

The course runs in 1st and 2nd quarter. The course start has been postponed two weeks, so it will start in week 37. Hence, the first lecture will be Monday, September 7.

The course is based on handouts (no textbook).

Examination

The final exam is oral, with grades on the 7-point marking scale. There are projects which must be passed during the course in order to attend the oral exam.

The exam date will be January 27. The exam will take place in U49B and U49D.

There will be a spørgetime (session for asking questions on the exam and the curriculum) Monday, January 25, at 14.15 in Imadas seminar room.

The curriculum is everything mentioned under the heading Reading in the list of lectures below (respecting the reading guides stated).

At the oral exam, you will draw an exam question delineating a part of curriculum which you are to present. The details of the exam format are described at the bottom of the list of exam questions.

Lectures

• September 7. Introduction to course. The I/O-model. (slides).

  Reading: The slides (except that last page). Section 1 of The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. S. Vitter. Communications of the ACM 31 (9): 1116--1127, 1988. Also in Proceedings of ICALP'87. Reading guide: set P=1 (i.e. forget about the parameter P), this parameter has since been removed from the basic model.

• September 10. More on classical sorting algorithms viewed in the I/O-model. Selection. (slides).

  Reading: Last page of the slides.

• September 14. Sorting by merging and distribution. (slides).

  Reading: Pages 1-8 of the slides. Sections 2, 3, and 5 of The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. S. Vitter. Communications of the ACM 31 (9): 1116--1127, 1988. Also in Proceedings of ICALP'87. Reading guide: set P=1 (i.e. forget about the parameter P), and do not read about other problems than sorting.

• September 17. Finding partition elements for sorting by distribution. Start on lower bound on sorting. (slides).

  Reading: External partition element finding. Lecture notes by L. Arge and M. G. Lagoudakis. Page 9-19 of the slides. Sections 5 and 4 of The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. S. Vitter. Communications of the ACM 31 (9): 1116--1127, 1988. Also in Proceedings of ICALP'87. Reading guide: set P=1 (i.e. forget about the parameter P), and do not read about other problems than sorting.

• September 21. End of lower bound on sorting. (slides).

  Reading: Page 20-22 of the slides. Lower bound on External Sorting. Lecture notes by L. Arge. Section 4 of The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. S. Vitter. Communications of the ACM 31 (9): 1116--1127, 1988. Also in Proceedings of ICALP'87. Reading guide: set P=1 (i.e. forget about the parameter P), and do not read about other problems than sorting.

• September 24. Permuting, upper and lower bounds. (slides). Handout and discussion of Project 1.

  Reading: The slides. Lower bound on External Permuting. Lecture notes by L. Arge. Section 4 of The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. S. Vitter. Communications of the ACM 31 (9): 1116--1127, 1988. Also in Proceedings of ICALP'87. Reading guide: set P=1 (i.e. forget about the parameter P), and do not read about other problems than permuting.

• September 28. End of lower bound for permuting. (slides). Start on searching.

  Reading: Same as last time, plus Section 1 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• October 1. Upper and lower bounds for static external comparison based searching. Dynamic searching: (a,b)-trees.

  Reading: Section 2 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• October 5. More on (a,b)-trees.

  Reading: Section 2 in External Memory Geometric Data Structures. Lecture notes by L. Arge. Amortized Analysis of (a,b)-Trees. Lecture notes by R. Fagerberg.

• October 8. End of amortized analysis of (a,b)-trees. Start on weight-balanced B-trees.

  Reading: Amortized Analysis of (a,b)-Trees. Lecture notes by R. Fagerberg. Section 3 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• October 26. Weight-balanced B-trees.

  Reading: Section 3 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• October 28. Persistent B-trees.

  Reading: Section 4 in External Memory Geometric Data Structures. Lecture notes by L. Arge. The teachers notes.

• October 29. End of Persistent B-trees.

  Reading: Same as last time.

• November 2. External interval trees. Handout and discussion of Project 2.

  Reading: Section 6 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• November 6. More on external interval trees.

  Reading: Section 6 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• November 9. External priority search trees. Start on External range trees.

  Reading: Section 7 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• November 11. More on External range trees.

  Reading: Section 8.1 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• November 16. External priority queue.

  Reading: Sections 2, 3, and 4 (until end of proof of Thm. 4 on page 12) in Heaps and heapsort on secondary storage by R. Fadel, K.V. Jakobsen, J. Katajainen, and J. Teuhola. In Theoretical Computer Science, 220 (2), 1999, pages 345-362. The teachers notes.

• November 19. Handback of reports from Project 1. List ranking.

  Reading: Section 3.1 in An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms by L. Arge, M.A. Bender, E. Demaine, B. Holland-Minkley, and J.I. Munro. In SIAM Journal on Computing, 36(6), 2007, pages 1672-1695. (For now, just disregard the word cache-oblivious in the text.)

• November 23. End of list ranking. Euler Tour on trees. DFS on trees.

  Reading: Section 3.2 in An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms by L. Arge, M.A. Bender, E. Demaine, B. Holland-Minkley, and J.I. Munro. In SIAM Journal on Computing, 36(6), 2007, pages 1672-1695. (For now, just disregard the word cache-oblivious in the text.) The teachers notes.

• November 30. External MST.

  Reading: Section 3.4 in An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms by L. Arge, M.A. Bender, E. Demaine, B. Holland-Minkley, and J.I. Munro. In SIAM Journal on Computing, 36(6), 2007, pages 1672-1695. (For now, just disregard the word cache-oblivious in the text.). Section 2 in On External-Memory MST, SSSP and Multi-way Planar Graph Separation by L. Arge, G.S. Brodal, L. Toma. In Journal of Algorithms, 53(2), 2004, pages 186-206.

• December 3. Handout of Project 3. More on external MST.

  Reading: As above. The teachers notes.

• Dec 7. More on external MST.

  Reading: As above.

• Dec 10. Discussion first task of of Project 3. External BFS.

  Reading: Section 1, 2, and 4 in External-Memory Breadth-First Search with Sublinear I/O by K. Mehlhorn and U. Meyer. In proceedings of 10th Ann. European Symposium on Algorithms (ESA), Lecture Notes in Computer Science vol. 2461, Springer, 2002, pages 723-735. Reading guide: set D=1 (single disk).

• Dec 14. Discussion second task of Project 3. External BFS in o(V) time.

  Reading: Section 3, 5.2, and 6 in External-Memory Breadth-First Search with Sublinear I/O by K. Mehlhorn and U. Meyer. In proceedings of 10th Ann. European Symposium on Algorithms (ESA), Lecture Notes in Computer Science vol. 2461, Springer, 2002, pages 723-735. Reading guide: set D=1 (single disk), and skip Section 5.1 on the randomized preprocessing phase (some of the statements regarding this have turned out not to hold). We discuss the deterministic version only (which requires reading Section 5.2).

• Dec 18. Discussion third task of Project 3 Cache-oblivious model. Cache-oblivious static searching. Start on cache-oblivious dynamic searching.

  Reading: Chapter Cache-oblivious Model by R. Fagerberg. In Encyclopedia of Algorithms, Ming-Yang Kao (ed.), Springer 2008. Chapter Cache-oblivious B-Tree by R. Fagerberg. In Encyclopedia of Algorithms, Ming-Yang Kao (ed.), Springer 2008. Sections 38.1 and 38.2.1 in Cache-Oblivious Data Structures by L. Arge, G.S. Brodal, and R. Fagerberg. Chapter 38 in Handbook of Data Structures and Applications, Dinesh Mehta and Sartaj Sahni (ed.), CRC Press, 2005.

• Dec 21. Cache-oblivious dynamic searching.

  Reading: Sections 1, 2, 3.1, and 3.2 in Cache-Oblivious Search Trees via Binary Trees of Small Height by G.S. Brodal, R. Fagerberg, and R. Jacob. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 39-48, 2002. Reading guide: You may skip any mentioning of BFS, DFS, and Inorder layout (only the van Emde Boas layout is in focus in this course). The implicit navigation in Section 2 is not curriculum.