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ørtz, ilg@imm.dtu.dk
Carsten Witt, cawi@imm.dtu.dk
Philip Bille, phbi@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.

• J. Carter and M. Wegman, Universal Classes of Hash Functions. J. Comp. Sys. Sci., 1977
• M. Fredman, J. Komlos and E. Szemeredi, Storing a Sparse Table with O(1) Worst Case Access Time, J. ACM., 1984
• Scribe notes from MIT
• Peter Bro Miltersen’s notes from Aarhus
• Slides
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Week 2: Amortized analysis and Union-Find.

Amortized Analysis:

• Rebecca Fiebrink’s notes on amortized analysis from Princeton.
• Pawel Winter’s notes on amortized analysis from DIKU.
• R. E. Tarjan: Amortized Computational Complexity, SIAM. J. on Algebraic and Discrete Methods Volume 6, Issue 2, pp. 306-318 (April 1985)

Union-Find:

• R. E. Tarjan and J. van Leeuwen: Worst-case Analysis of Set Union Algorithms, JACM, 1984 .
• R. E. Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm, JACM, 1975.
• Alstrup et al.: Union-Find with Constant Time Deletions, ICALP 2005.
• R. Seidel: Top-Down Analysis of Path Compression: Deriving the Inverse-Ackermann Bound Naturally (and Easily), SWAT 2006.

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.

• P. van Emde Boas, Preserving Order in a Forest in less than Logarithmic Time, FOCS, 1975
• Dan E. Willard, Log-Logarithmic Worst-Case Range Queries are Possible in Space Θ(n), Inf. Process. Lett., 1983
• Scribe notes from MIT
• Slides (computational models)
• Slides (predecessor data structures)
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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

• S. Alstrup, J. P. Secher, M. Spork: Optimal On-Line Decremental Connectivity in Trees, Inf. Process. Lett., 1997
• S. Alstrup, J. P. Secher, M. Thorup: Word encoding tree connectivity works. SODA, 2000
• Scribe notes from MIT
• Slides
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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

• S. Alstrup, C. Gavoille, H. Kaplan, T. Rauhe, Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment, Theory of Comput. Sys., 2004
• D. Harel, R. E. Tarjan: Fast Algorithms for Finding Nearest Common Ancestors. SIAM J. Comput., 1984
• Scribe notes from MIT
• Slides
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Week 6: Persistent data structures.

• H. Kaplan, Persistent Data Structures, In Handbook on Data Structures and Applications, D. Mehta and S. Sahni, editors, CRC Press, 2005.
• N. Sarnak and R. E. Tarjan, Planar Point Location Using Persistent Search Trees, CACM, 1986.
• J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, Making Data Structures Persistent, JCSS, 1989.
• P.F. Dietz, Fully Persistent Arrays, WADS 1989.
• G. F. Italiano and R.Raman, Topics in Data Strutures.
• Slides.
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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

• S. Droste, T. Jansen, I. Wegener, On the analysis of the (1+1) evolutionary algorithm, Theoretical Computer Science, vol. 276, 51-81, 2002
• I. Wegener: Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions, in: Sarker, Mohammadian, Yao (eds.): Evolutionary Optimization, 349-369, Kluwer, 2002
• Slides
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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

• F. Neumann and I. Wegener: Randomized local Search, evolutionary algorithms, and the minimum spanning tree problem, Theoretical Computer Science, vol. 378, 32-40, 2007

• O. Giel and I. Wegener, Evolutionary Algorithms and the Maximum Matching Problem, STACS 2003, 415-426, Springer, 2003

• Slides

• 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

• I. Wegener: Simulated Annealing Beats Metropolis in Combinatorial Optimization, ICALP 2005, 589-601, Springer, 2005

• K. Meer: Simulated Annealing versus Metropolis for a TSP instance, Information Processing Letters, vol. 104, 216-219, 2007
• Slides (version containing all overlays); printer-friendly version

• 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.

• Jeff Erickson: Non-Lecture K: Approximation Algorithms
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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

• Jeff Erickson: Non-Lecture K: Approximation Algorithms
• Hochbaum and Shmoys: A unified approach to approximation algorithms for bottleneck problems
• S. Arora: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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”.

Advertisement