DM808 I/OEfficient 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:
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 7point 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/Omodel.
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): 11161127,
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. Btrees.
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 Btrees.
Reading: Section 2 in External
Memory Geometric Data Structures. Lecture notes by L. Arge.
 February 27. Questions on Project 1. Weightbalanced
Btrees. Start on persistent Btrees.
Reading: Section 3 in External
Memory Geometric Data Structures. Lecture notes by L. Arge.
 February 29. Persistent Btrees.
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 345362.
 April 22. List ranking.
Reading: Section 3.1 in An Optimal
CacheOblivious Priority Queue and its Application to Graph
Algorithms by L. Arge, M.A. Bender, E. Demaine,
B. HollandMinkley, and J.I. Munro. In SIAM Journal on Computing,
36(6), 2007, pages 16721695. (For now, just disregard the word
cacheoblivious in the text.)
 April 25. Euler Tour on trees. DFS on trees.
Reading: Section 3.2 in An Optimal
CacheOblivious Priority Queue and its Application to Graph
Algorithms by L. Arge, M.A. Bender, E. Demaine,
B. HollandMinkley, and J.I. Munro. In SIAM Journal on Computing,
36(6), 2007, pages 16721695. (For now, just disregard the word
cacheoblivious in the text.)
 April 30. External MST.
Reading: Section 2 in On ExternalMemory
MST, SSSP and Multiway Planar Graph Separation by L. Arge,
G.S. Brodal, L. Toma. In Journal of Algorithms, 53(2), 2004, pages
186206.
 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 ExternalMemory
BreadthFirst 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
723735. 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
ExternalMemory BreadthFirst 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 723735. 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. Cacheoblivious
model. Cacheoblivious static searching.
Reading: Sections 38.1 and 38.2.1 in CacheOblivious 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. Cacheoblivious dynamic searching.
Reading: Sections 1, 2, 3.1, and 3.2 in CacheOblivious
Search Trees via Binary Trees of Small Height by G.S. Brodal,
R. Fagerberg, and R. Jacob. In Proc. 13th Annual ACMSIAM Symposium on
Discrete Algorithms (SODA), pages 3948, 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.
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)

