Archive 2011

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.

• 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: 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
• Cormen, Rivest, Leiserson, Introduction to Algorithms, 3rd edition, Chap. 20.
• Slides
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Week 3: 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 4: 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 5: 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 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: 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
• D. Sudholt, General Lower Bounds for the Running Time of Evolutionary Algorithms, in: Proc. of Parallel Problem Solving from Nature (PPSN 2010), LNCS 6238, 124-133, Springer, 2010.
• Lecture notes
• Slides (printer-friendly version)
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Week 8: 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
• Chapters 5 and 6 in F. Neumann and C. Witt, Bioinspired Computation in Combinatorial Optimization – Algorithms and Their Computational Complexity,  Natural Computing Series, Springer, 2010
• Lecture notes
• Slides (printer-friendly version)
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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

• Chapters 7 in F. Neumann and C. Witt, Bioinspired Computation in Combinatorial Optimization – Algorithms and Their Computational Complexity,  Natural Computing Series, Springer, 2010
• Lecture notes
• Slides (printer-friendly version)
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Week 10: 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

• Lecture notes
• Slides (printer-friendly version)

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

• David P. Williamson and David Shmoys: The Design of Approximation Algorithms (sections 1.1., 2.2, and 2.4)
• Jeff Erickson: Non-Lecture K: Approximation Algorithms
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

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.

• David P. Williamson and David Shmoys: The Design of Approximation Algorithms (page 24-28).
• Jeff Erickson: Non-Lecture K: Approximation Algorithms
• Zoltán Király: Better and Simpler Approximation Algorithms for the Stable Marriage Problem (page 3-10)
• Exercises (Please hand in the mandatory one through Campusnet using the template provided)

Advertisement