Archive 2012


State-of-the-art algorithmic techniques and models for massive data sets.

Official description


Inge Li Gø

When and where

Monday 8.15- 10.  Bldg. 208, Aud. 51.

Monday 10-12. Bldg. 210, Rooms 112 and 118.


The weekplan is preliminary. It will be updated during the course. Under each week there is a number of suggestions for reading material regarding that weeks lecture. It is not the intention that you read ALL of the papers. It is merely a list of papers and notes where you can read about the subject discussed at the lecture.

Week 1: Introduction and Hashing: Chained, Universal, and Perfect.

Week 2Predecessor Data Structures: x-fast tries and y-fast tries.

Week 3: Decremental Connectivity in Trees: Cluster decomposition, Word-Level Parallelism.

Week 4Nearest Common Ancestors: Distributed data structures, Heavy-path decomposition, alphabetic codes.

Week 5: Amortized analysis and Union-Find.

Amortized Analysis:


Week 6: Range Reporting: Range Trees, Fractional Cascading, and kD Trees.

Week 7: Persistent data structures.

Week 8: String matching.

Week 9: String Indexing: Dictionaries, Tries, Suffix trees, and Suffix Sorting.

Week  10: Introduction to approximation algorithms. TSP, k-center, vertex cover.

You can also read about some of these problems in Kleinberg and Tardos: “Algorithm Design”, V.V. Vazirani: Approximation Algorithms, Cormen, Leierson, Rivest, and Stein: “Introduction to Algorithms”.

Week 11:  Approximation algorithms:  Set Cover, stable matching.

Week 12: External Memory: I/O Algorithms, Cache-Oblivious Algorithms, and Dynamic Programming

Week 13: Round up,  Questions,  and further Perspectives.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s