DM808 I/O-Efficient Algorithms and Data Structures

Spring 2008
Rolf Fagerberg

Official Course Description

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

Time and Place

The schedule in the 3rd quarter is as follows:

• Wednesdays 10.15 to 12.00 in Imadas seminar room.
• Fridays 10.15 to 12.00 in Imadas seminar room.

The schedule in the 4th quarter is as follows:

• Tuesdays 12.15 to 14.00 in U49D.
• Fridays 12.15 to 14.00 in U49C.

The course starts in week 5, and runs in 3rd and 4th quarter. The first lecture is Wednesday, January 30.

The course is based on handouts (no textbook).

Examination

The exam is oral, with grades on the 7-point marking scale. Programming projects must be passed in order to attend the exam.

The exam date will be June 6, and the exam will take place in U49C and U49D.

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.

There will be a spørgetime (session for asking questions on the exam and the curriculum) Wednesday, June 4, at 12.15 in Imadas seminar room.

Lectures

• January 30. Introduction to course (slides). The I/O-model.

  Reading: The slides.

• February 1. Sorting by merging and distribution, selection (slides).

  Reading: The slides. 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 and permuting. External partition element finding. Lecture notes by L. Arge and M. G. Lagoudakis.

• February 6. Lower bound for sorting (slides). Upper and lower bound for permuting (slides).

  Reading: The slides. Lower bound on External Permuting/Sorting. Lecture notes by L. Arge.

• February 13. End of lower bound for permuting. B-trees.

  Reading: Sections 1 and 2 in External Memory Geometric Data Structures. Lecture notes by L. Arge.

• February 15. Handout and discussion of Project 1. Amortized analysis of B-trees.

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

• February 27. Questions on Project 1. Weight-balanced B-trees. Start on persistent B-trees.

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

• February 29. Persistent B-trees.

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

• March 5. External interval trees.

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

• March 12. External interval trees.

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

• March 14. Handback of reports from Project 1.Handout and discussion of Project 2. External priority search trees.

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

  No teaching in Weeks 12 (Easter break), 13, and 14 (Exam break).

• April 8. External range trees.

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

• April 15. External priority queue.

  Reading: Sections 2, 3, and 4 (until end of proof of Thm. 4) 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.

• April 22. 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.)

• April 25. 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.)

• April 30. External MST.

  Reading: 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.

• May 6. Handout and discussion of Project 3. More on external MST.

  Reading: As above.

• May 9. Discussion of Project 3.

• May 13. Discussion 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).

• May 16. 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).

• May 20. Cache-oblivious model. Cache-oblivious static searching.

  Reading: 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 (Edt.), CRC Press, 2005.

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