DM207 I/OEfficient Algorithms and Data Structures
Fall 2015
Rolf Fagerberg
Official Course Description
See the
course
description at the web pages of the faculty.
Time and Place
The course starts Monday, August 31.
The schedule is as follows:
Teaching material
The course is based on handouts (no textbook).
Examination
The final exam is oral, with grades on the 7point marking scale. The
exam date is January 26. There are projects which must be passed during
the course in order to attend the oral exam.
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 and curriculum are described at the bottom of the list of
exam topics.
Lectures
Date 
Time 
Room 
Contents 
Reading 
Monday, August 31 
0911 
Imada seminar room 
Introduction to the course. The I/Omodel.

Pages 118 of the introduction sldes.
For the original appearance of the I/Omodel, see 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 (not curriculum). reading guide: set P=1
[i.e. forget about the parameter P], this parameter has since been
removed from the basic model.

Wednesday, September 2 
0810 
Imada seminar room 
Overview of basic bounds in the I/Omodel. Stacks, and
queues. Selection. Multiway mergesort.

Pages 1922 of the introduction 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).
Pages 16 of the slides on sorting.

Monday, September 7 
0911 
Imada seminar room 
Sorting by distribution: multiway quicksort.

Pages 78 of the
slides. External
partition element finding, lecture notes by L. Arge and
M. G. Lagoudakis.

Wednesday, September 9 
0810 
Imada seminar room 
Start on lower bound proof for sorting.

Pages 919 of the slides.
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 (not curriculum). Reading guide: set P=1
[i.e. forget about the parameter P], and do not read about other
problems than sorting.

Monday, September 14 
0911 
Imada seminar room 
End of lower bound proof for sorting.

Pages 1122 of the slides.

Wednesday, September 16 
0810 
Imada seminar room 
CPU time for multiway mergesort. Permuting, upper and lower bounds.

Notes from
lecture on CPU time for multiway mergesort. The
slides on permuting. 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 (not curriculum) Reading guide: set P=1
[i.e. forget about the parameter P], and do not read about other
problems than permuting.

Monday, September 21 
0911 
Imada seminar room 
Searching. Multiway search trees (alias (ab)trees or Btrees).

Section 1 and page 3 in External Memory
Geometric Data Structures, lecture notes by L. Arge. Page 1 of
notes from lectures on (a,b)trees.

Wednesday, September 23 
0810 
Imada seminar room 
Handout and discussion of Project 1.
Rebalancing of (a,b)trees.

Rest of section 2 in External Memory
Geometric Data Structures, lecture notes by L. Arge. Rest of
notes from lecture on
(a,b)trees.

Monday, September 28 
0911 
Imada seminar room 
Amortized analysis of rebalancing of (a,b)trees.

Page 14 of Amortized
Analysis of (a,b)Trees, lecture notes by R. Fagerberg.
Notes from lecture on
amortized rebalancing of (a,b)trees.

Wednesday, September 30 
0911 
Imada seminar room 
End of amortized analysis of rebalancing of (a,b)trees. Lower bounds
for searching.

Page 14 of Amortized
Analysis of (a,b)Trees, lecture notes by R. Fagerberg.
Notes from lecture on
amortized rebalancing of (a,b)trees.
Notes from lecture on
optimality of (a,b)trees for comparison based searching.

Monday, October 5 
0911 
Imada seminar room 
No lecture due to lecturer traveling.


Wednesday, October 7 
0810 
Imada seminar room 
Weightbalanced Btrees.

Section 3 in External Memory Geometric Data
Structures, lecture notes by L. Arge.
Notes from lecture on
weightbalanced Btrees.

Monday, October 19 
0911 
Imada seminar room 
External priority queues.

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. Notes
from lecture on external priority queues.

Wednesday, October 21 
0810 
Imada seminar room 
External interval trees.

Section 6 in External Memory
Geometric Data Structures, lecture notes by
L. Arge. Notes from
lecture on external interval trees (part I).

Monday, October 26 
0911 
Imada seminar room 
More on interval trees.

Notes from
lecture on external interval trees (part II).

Wednesday, October 28 
0810 
Imada seminar room 
End of external interval trees. Start on external priority search
trees.

Section 7 in External Memory
Geometric Data Structures, lecture notes by
L. Arge.

Monday, November 2 
0911 
Imada seminar room 
End of external priority search trees.

Section 7 in External Memory
Geometric Data Structures, lecture notes by
L. Arge.

Wednesday, November 4 
0810 
Imada seminar room 
External range trees.

Section 8.1 (and "8.0") in External
Memory Geometric Data Structures, lecture notes by L. Arge.

Monday, November 9 
0911 
Imada seminar room 
No lecture.


Wednesday, November 11 
0810 
Imada seminar room 
Handback of project 1. List ranking.

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.)

Monday, November 16 
0911 
Imada seminar room 
Feedback on project 1. End of list ranking.


Wednesday, November 18 
0810 
Imada seminar room 
Algorithms on trees: Euler tour, DFS. Start on BFS in general undirected
graphs.

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 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).

Monday, November 23 
0911 
Imada seminar room 
External BFS in undirected graphs in o(V) time.

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).

Wednesday, November 25 
0810 
Imada seminar room 
Start on external MST, version based on Prim's algorithm.

Section 2.1 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.
[The same material is covered in section 3.4.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.)]

Monday, November 30 
0911 
Imada seminar room 
More on external MST, version based on Boruvka's algorithm.

Section 2.2.1 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.
The same material is covered in section 3.4.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.) Note that the method for
distributing the IDs of the new connected components during a
contraction stage is not the same in the two papers. In class, we used
the method from the latter of the two papers.

Wednesday, December 2 
0810 
Imada seminar room 
End of external MST, the superphase algorithm. Handout and discussion of
Project 2.

Section 2.2.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.

Monday, December 7 
0911 
Imada seminar room 
End of the superphase algorithm. The cacheoblivious
model.

Section 38.1 in CacheOblivious Data Structures by L. Arge,
G.S. Brodal, and R. Fagerberg [handout in class]. In Handbook of Data
Structures and Applications, Dinesh Mehta and Sartaj Sahni (ed.), CRC
Press, 2005. The slides on the
cacheoblivious model (up to page 21).

Wednesday, December 9 
0810 
Imada seminar room 
Cacheoblivious double forloop. Cacheoblivious static searching.

Section 38.2.1 in CacheOblivious Data Structures by L. Arge,
G.S. Brodal, and R. Fagerberg [handout in class]. In Handbook of Data
Structures and Applications, Dinesh Mehta and Sartaj Sahni (ed.), CRC
Press, 2005. The slides on the
cacheoblivious model (pages 1523).

Monday, December 14 
0911 
Imada seminar room 
Cacheobliviuos range search. Cacheobliviuos dynamic
searching.

Sections 38.2.1 and 38.3.1 in CacheOblivious Data
Structures by L. Arge, G.S. Brodal, and R. Fagerberg [handout in
class]. In Handbook of Data Structures and Applications, Dinesh Mehta
and Sartaj Sahni (ed.), CRC Press, 2005. The
slides on the cacheoblivious model
(pages 2432).

Wednesday, December 16 
0810 
Imada seminar room 
End of cacheoblivious dynamic searching.

Sections 38.3.1 in CacheOblivious Data Structures by L. Arge,
G.S. Brodal, and R. Fagerberg [handout in class]. In Handbook of Data
Structures and Applications, Dinesh Mehta and Sartaj Sahni (ed.), CRC
Press, 2005. Sections 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.

Monday, December 21 
0911 
Imada seminar room 
Cacheobliviuos sorting.

Section 38.2.2 in CacheOblivious Data
Structures by L. Arge, G.S. Brodal, and R. Fagerberg [handout in
class]. In Handbook of Data Structures and Applications, Dinesh Mehta
and Sartaj Sahni (ed.), CRC Press, 2005. The
slides on the cacheoblivious model
(pages 3344).

Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)

