DM207 I/OEfficient Algorithms and Data Structures
Fall 2011
Rolf Fagerberg
Official Course Description
See the
course
description at the web pages of the faculty.
Time and Place
The course starts Wednesday, August 31 (the teacher has overlapping other
obligations Monday, August 29).
The schedule in the 1st quarter is as follows:
The schedule in the 2nd quarter is as follows:
with the following exceptions:
 Monday, Nov 7 (instead of Tuesday, Nov 8)
10:15 to 12:00 in
U49B
 Thursday, Nov 10 in
U49C
 Monday, Nov 21 (instead of Tuesday, Nov 22)
10:15 to 12:00 in
U57 (1011) and
U141 (1112).
 In week 48, only the Thursday lecture will take place (Thursday,
December 1).
 Monday, Dec 5 (instead of Tuesday, Dec 6)
10:15 to 12:00 in
U57 (1011) and
U17 (1112).
 Monday, Dec 19 (instead of Tuesday, Nov 29)
10:15 to 12:00 in U26
 Tuesday, Dec 20 there will only be lectures 15:15 to 16:00 (still
in Imadas seminar room).
Teaching material
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 is January 24. The exam will take place in
Imadas seminar room, with
preparation in U49.
There will be a spørgetime (session for asking questions on the exam and
the curriculum) Monday, January 23, at 10.15 in
U49C.
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 one topic from a list
of exam topics. The topic delineates the part of curriculum which you are
to present. The full details of the exam format are described at the bottom
of the list of exam topics.
Lectures
 August 31. Introduction to course. The I/Omodel.
Reading: The slides, pages
119. 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 (reading guide: set P=1 [i.e. forget about the parameter P], this
parameter has since been removed from the basic model.)
 September 5. Stacks, and queues. Selection.
Reading: Last page two pages of the
slides. If you want a more detailed
reminder of the classic linear selection algorithm, it can be found in any
good textbook on algorithms and data structures, e.g. Section 9.3 in
Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein, 3rd
edition, MIT Press, 2009 (not curriculum).
 September 7. More on classical sorting algorithms viewed in
the I/Omodel. Optimal sorting in the I/Omodel: multiway mergesort, start
on lower bound proof.
Reading: Pages 16 and 915 of the slides.
 September 12. End of lower bound proof for sorting.
Reading: Pages 1620 and 22 of the slides.
 September 14. Last bits of lower bound proof for
sorting. Sorting by distribution: multiway quicksort.
Reading: Pages 21 and 78 of the
slides. External
partition element finding, lecture notes by L. Arge and
M. G. Lagoudakis. For the original appearance of the upper and lower bounds
on sorting, see sections 2, 3, 4, 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 (Reading guide: set P=1 [i.e. forget about the parameter P], and
do not read about other problems than sorting.)
 September 19. Handout and discussion of
Project 1. Start on permuting, upper and
lower bounds.
Reading: Pages 17 of the slides.
 September 21. More details of permuting lower bound proof.
Reading: Pages 17 of the slides.
For the original appearance of the upper and lower bounds on permuting, see
sections 2, 3, 4, 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 (Reading guide: set P=1 [i.e. forget about the parameter P], and
do not read about other problems than permuting.)
 September 26. A few last math details from permuting lower
bound proof. Start on searching: upper and lower bounds for static external
comparison based searching.
Reading: Same as last time, plus Section 1 and page 3 in
External Memory Geometric Data
Structures, lecture notes by L. Arge.
Overview over which machines in the Imada
terminal room not to use for experiments.
 September 28. Dynamic searching: (a,b)trees (aka. Btrees).
Reading: Page 4 in External Memory
Geometric Data Structures, lecture notes by L. Arge. Pages 14 in
notes from lectures on (a,b)trees.
 October 3. More on (a,b)trees.
Reading: Rest of section 2 in External
Memory Geometric Data Structures, lecture notes by L. Arge. Pages
56 in notes from lecture on
(a,b)trees. Pages 14 in
Amortized Analysis of
(a,b)Trees, lecture notes by R. Fagerberg.
Notes from lecture on amortized
rebalancing of (a,b)trees.
 October 5. End of amortized analysis of (a,b)trees.
Reading: Rest of
Amortized Analysis of
(a,b)Trees, lecture notes by R. Fagerberg.
Notes from lecture on
amortized rebalancing of (a,b)trees.
 October 10. Weightbalanced Btrees.
Section 3 in External Memory Geometric Data
Structures, lecture notes by L. Arge.
Notes from lecture on
weightbalanced Btrees.
 October 12. Discussion of Project 1. End of weightbalanced
Btrees.
Reading: Same as last time.
 November 7. Handback of Project 1. Start on external priority
queues.
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. Notes from
lecture on external priority queues.
 November 10. Handout and discussion of
Project 2. More on external priority queues.
Reading: Same as last time.
 November 15. End of external priority queues. Start on
external interval trees.
Reading: Section 6 in External Memory
Geometric Data Structures, lecture notes by
L. Arge. Notes from
lecture on external interval trees (part I).
 November 17. More on external interval trees.
Reading: Same as last time.
 November 21. End of external interval trees.
Reading: Notes
from lecture on external interval trees (part II).
 November 24. External priority search
trees.
Reading: Section 7 in External Memory
Geometric Data Structures, lecture notes by L. Arge.
 December 1. End of external priority search trees.
Reading: Same as last time.
 December 5. External range trees.
Reading: Section 8.1 (and "8.0") in
External Memory Geometric Data
Structures, lecture notes by L. Arge.
 December 8. End of external range trees. Start on list ranking.
Reading: Same as last time, plus first pages of
notes from lecture on list ranking
and 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.)
 December 13. End of list ranking.
Reading: Rest of notes from
lecture on list ranking. 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.)
 December 15. Algorithms on trees: Euler tour, DFS. Start on
BFS on undirected graphs. Handout of
Project 3.
Reading: Notes from lecture on
Euler tour. 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.) 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).
 December 19. 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).
 December 20. Cacheoblivious model. Cacheoblivious
static searching.
Reading: Chapter Cacheoblivious Model 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. In Handbook of Data Structures
and Applications, Dinesh Mehta and Sartaj Sahni (ed.), CRC Press, 2005.
 December 22. Handback of Project 2. Cacheoblivious dynamic
searching.
Reading: Section 38.3.1 in CacheOblivious Data Structures by
L. Arge, G.S. Brodal, and R. Fagerberg. In Handbook of Data Structures and
Applications, Dinesh Mehta and Sartaj Sahni (ed.), CRC Press, 2005.
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)

