





Outline of course 



Intro: I/Omodel and fundamental bounds
Sorting and Searching: External sorting, Btrees 
[AV] sec 3+5
[Agis] sec 1, 2, 3.13.2, [AL] [Mehlhorn], [Ads] sec 2.0 


Sorting and Searching: Buffertrees, lower bounds  [Agis] sec 3.3, [Abuffer]
sec 14, [Alower]
[AV] (only stuff on sorting/permuting lower bound) 


Graph problems: List ranking, algorithms on trees.  [CGGTVV], sec 36, [Abuffer] sec 4.1 


Graph problems: DepthFirst and BreadthFirst Search  [CGGTVV], sec 7, [BGVW], [MR] sec 5.1. 3.1 


Graph problems: Minimal Spanning Tree,
Shortest paths (tournement tree) 
[ABT] sec 2. (note on vertex contraction later)
[KS] sec 3. 


Graph problems: Shortest paths, discussion of other results,
lower bounds (model discussion and SPN, CC, list ranking bounds) 
[KS] sec 5.2, [T], (review
of [ABW])
[CGGTVV] sec. 2, [Aobbd] sec 2.3lemma 2 (review of [MR] sec 24, [AKL] sec 14]) 


Graph problems: Graph blocking
Batched geometric problems: Distribution sweeping, external segment trees, batched filtering 
[NGV]
[Agis] sec 4.14.2. [GTVV] sec 2 


Batched geometric problems: External extended segment trees
and fractional cascading 
[AVV] sec 12, [Agis] 4.3.14.3.2 






Batched geometric problems: Overview of results (line segment
intersection, convex hull, randomized algorithms), lower bounds Geometric searching problems: Weightbalanced and persistent Btrees 
([Agis] sec 4.3.34.4, [AVV]
sec 3,
[CGGTVV], [CFMMR]sec 6, [AM] sec 1) [Ads] sec 2.1, [AVi] sec 3.1, [BGOSW], ([VV]) 


Geometric searching problems: External interval tree, logarithmic
method, dynamic point location 
[Ads] sec 34, [AVi],
[AABV] sec 12, [AVa] sec 13 






Geometric searching problems: External priority search
tree,
external range tree, kdB trees 
[Ads] sec 56, [ASV] sec 1+34,[AAPV] 


Geometric searching problems: Otree, overview of other
worstcase and heuristic results 
[KS] sec 4, [Ads] sec 79, [NW] 