Archive 2011


State-of-the-art algorithmic techniques and models for massive data sets. The course cover 3 major topics:

  • Advanced data structures
  • Approximation algorithms
  • Time complexity analysis of randomized search heuristics

Official description


Inge Li Gø

When and where

Monday 8.15- 10. Building 308, auditorium 11.

Monday 10-12. Group exercises in building 322, room 033.


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.

Part I: Advanced Data Structures

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

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

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

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

Week 5: Amortized analysis and Union-Find.

Amortized Analysis:



  • Slides
  • Exercises (Please hand in the mandatory one through Campusnet using the template provided).
  • You can also read about both amortized analysis and Union-Find data structures in Cormen, Leierson, Rivest, and Stein: “Introduction to Algorithms”.

Week 6: Persistent data structures.

Part II: Randomized Search Heuristics

Week 7: Simple Evolutionary Algorithms (EAs) and Randomized Local Search (RLS): Techniques for Runtime Analysis, Example Problems

Week 8: Simple EAs and RLS: Analysis for Minimum Spanning Trees and Maximum Matchings

Week 9: Simple EAs and RLS: Analysis for Makespan Scheduling

Week 10: Simulated Annealing Beats Metropolis in Combinatorial Optimization

  • Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Part III: Approximation Algorithms

Week  11: 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 12:  Approximation algorithms: Set Cover, stable matching.


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 )

Google+ photo

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

Connecting to %s