Time & Place

• Lectures: Thursday 15-17 @ CAB G52
  
• Exercises: Thursday 17-18 @ CAB G52

Instructors

Lecturer: Riko Jacob

CAB J 21.2/ Tel: (01) 632-7403. e-mail: rjacob@inf.ethz.ch

Lecturer: Peter Widmayer

CAB H 15/ Tel: (01) 632-7400. e-mail: widmayer@inf.ethz.ch

Assistant: L. Shankar Ram

CAB G39.3/ Tel: (01) 632-7372. e-mail: lshankar@inf.ethz.ch

Schedule

Lectures	Materials	Exercises	References
#1 (October 27) Introduction I/O model Sorting Permuting	[PDF] [PDF] [ Notes] [PDF]	[PDF, hints]	[AV88]
#2 (November 03) Spatial data structures B-trees, (a,b)-trees Linear and extendible hashing	[PDF] [Notes on (a,b)-trees] [PDF] [Linear and Extendible Hashing]	[PDF]
#3 (November 10) Cache-oblivious algorithms	[PDF]	[PDF]	[AL93] [AV88] [BBFG+03] [BF02] [BF03] [BFJ02] [FLPR99] [HK81] [Pro99] [ST85]
#4 (November 17) Cache Oblivious Search Trees	See previous lecture	[PDF]
#5 (November 24) Project Discussion	Refer to TWIKI
#6 (December 01) Project Discussion	Refer to TWIKI
#7 (December 08) Project Discussion Cache Oblivious Sorting	For FunnelSorting, refer to the notes of Lecture #3		[BF02] [FLPR99] [BFV04]
#8 (December 15) Buffer Trees	[PDF]		[Arg03]
#9 (December 22) More on Buffer Trees
#10 (January 12) Full-Text Indexes and String B-Trees	[PDF]		[FG99] [KS03]
#11 (January 19) Detailed Analysis of String B-Trees	[PDF]
#12 (January 26) Text Index Construction (Suffix Arrays)	[PDF]	[PDF]
#13 (February 02) External Memory Graph Algorithms	[Slides in TWiki]	[PDF]	[Chap. 4, MSS03]
#14 (February 09) BFS Algorithms	[Slides in TWiki]		[Chap. 4, MSS03]

Course Description

Computer systems usually have an entire hierarchy of memory levels, with each level having its own performance characteristics. Typical memory levels are: CPU registers, several levels of memory cache, main memory (RAM), and secondary memory (disk). Traditionally, the design of algorithms does not take this memory hierarchy into account, but assumes a model with a single level of main memory.

In an increasing number of problems, the amount of data to be processed is far too massive to fit into internal memory. Examples include data collections in astronomy, geology, meteorology, and finance, as well as web search engines, VLSI verification, computer graphics, and geographic information systems (GIS). In such applications, the amount of data may be measured in terabytes.

When dealing with data sets of sizes exceeding main memory, communication between the fast internal memory and the slow external memory is often the performance bottleneck, and the analysis of algorithms under the assumption of a single level of memory may be meaningless.

Instead, a more realistic measure of the efficiency of an algorithm is the number of I/O-operations performed between internal memory and disk. Algorithms designed to minimize this number are termed external memory algorithms.

In this course, we will study the design and analysis of efficient external memory algorithms and data structures. Different paradigms for efficiently solving problems in external memory will be presented, and a number of specific algorithms from areas like sorting and searching, computational geometry, and graphs will be covered.

Language

English

Last modified by L. Shankar Ram.