DM207 I/OEfficient 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:
The schedule in the 2nd quarter is as follows:
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 7point 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/Omodel.
(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): 11161127,
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/Omodel. Selection.
(slides).
Reading: Last page of the slides.
 September 14. Sorting by merging and distribution.
(slides).
Reading: Pages 18 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): 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.
 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 919 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): 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.
 September 21. End of lower bound on
sorting. (slides).
Reading: Page 2022 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): 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.
 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): 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 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
weightbalanced Btrees.
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. Weightbalanced Btrees.
Reading: Section 3 in External Memory
Geometric Data Structures. Lecture notes by L. Arge.
 October 28. Persistent Btrees.
Reading: Section 4 in External
Memory Geometric Data Structures. Lecture notes by L. Arge. The
teachers notes.
 October 29. End of Persistent Btrees.
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 345362. The
teachers notes.
 November 19. Handback of reports from Project 1. 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.)
 November 23. End of list ranking. 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.) The teachers
notes.
 November 30. External MST.
Reading: Section 3.4 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.). 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.
 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 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).
 Dec 14. Discussion second task of
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).
 Dec 18. Discussion third task of
Project 3 Cacheoblivious model. Cacheoblivious
static searching. Start on cacheoblivious dynamic searching.
Reading: Chapter Cacheoblivious Model by R. Fagerberg. In
Encyclopedia of Algorithms, MingYang Kao (ed.), Springer 2008. Chapter
Cacheoblivious BTree by R. Fagerberg. In Encyclopedia of
Algorithms, MingYang Kao (ed.), Springer 2008. 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 (ed.), CRC Press, 2005.
 Dec 21. 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)

