Archive 2010

Contents

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

Teachers

Inge Li Gørtzilg@imm.dtu.dk
Carsten Wittcawi@imm.dtu.dk
Philip Billephbi@imm.dtu.dk

When and where

Monday 8.15- 10. Building 308, auditorium 11.

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

Weekplan

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.

Reading material: It is not the intention that you read all the papers and notes below. It is merely a list of papers and notes where you can read about the subject discussed at the lecture.

Week 2: Amortized analysis and Union-Find.

Amortized Analysis:

Union-Find:

General:

  • 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 3: Predecessor Data Structures: Computational Models, x-fast tries, and y-fast tries.

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

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

Week 6: Persistent data structures.



Part II: Randomized Search Heuristics

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

Week 9 (12.04.2010): Simple EAs and RLS: Analysis for Minimum Spanning Trees and Maximum Matchings

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

Week 10 (19.04.2010): 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  (26.04.2010): Introduction to approximation algorithms. Vertex cover, TSP, Set Cover.

Week 12 (03.05.2010) metric k-center, LP rounding, FPTAS.

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

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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