6.854 - Advanced Algorithms

David Karger

Handout #1, September 9, 2009 -- Class Outline

Summary:
The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are ``efficient,'' and even the model of computation can vary widely from area to area. In this second class in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms; network optimization; parallel algorithms; computational geometry; online algorithms; external memory, cache, and streaming algorithms; and data structures.

Goals:
Our hope is that this class will confer

Class webpage: http://courses.csail.mit.edu/6.854/

Lecturer: David Karger, 32-G592, x8-6167. karger@mit.edu. URL: http://people.csail.mit.edu/karger/
TA: Aleksandar Zlateski, Location TBA. zlateski@mit.edu. URL: http://people.csail.mit.edu/zlateski

Content: The goal is for the class to be broad rather than deep. Our plan is to touch upon the following areas. This is a tentative list of topics that are likely be covered in the class.

Data Structures:
More advanced solutions to basic data structuring problems: Fibonacci heaps. Van Emde Boas priority queues. Dynamic data structures for graph connectivity/reachability.
Bit Tricks:
Word-level parallelism. Transdichotomous model. $o(n \log n)$ integer sorting.
String Algorithms:
Rabin-Karp fingerprinting algorithm. Suffix trees.
Maximum Flows:
Augmenting paths and push-relabel methods. Min-cost flows. Bipartite matching.
Linear Programming:
Formulation of problems as linear programs. Duality. Simplex, interior point, and ellipsoid algorithms.
Online Algorithms:
Ski rental. Paging. The $k$-server problem. List ordering and move-to-front.
Approximation Algorithms:
One way of coping with NP-hardness. Greedy approximation algorithms. Dynamic programming and weakly polynomial-time algorithms. Linear programming relaxations. Randomized rounding. Vertex cover, wiring, and TSP.
Fixed-Parameter Algorithms:
Another way of coping with NP-hardness. Parametrized complexity. Kernelization. Vertex cover. Connections to approximation.
Parallel Algorithms:
PRAM. Pointer jumping and parallel prefix. Tree contraction. Divide and conquer. Randomized symmetry breaking. Maximal independent set.
External-Memory Algorithms:
Accounting for the cost of accessing data from slow memory. Sorting. B-trees. Buffer trees. Cache-oblivious algorithms for matrix multiplication and binary search.
Computational Geometry:
Convex hull. Line-segment intersection. Sweep lines. Voronoi diagrams. Range trees. Seidel's low-dimensional LP algorithm.
Streaming Algorithms:
Sketching. Distinct and frequent elements.

Prerequisites: We assume that the reader has had an undergraduate class in Algorithms (6.046) and some exposure to probability (6.041 or 6.042 are more than sufficient). Complexity Theory (6.045) is a bonus.

Requirements:
Scribing and/or grading (5%).
Help scribe a lecture in LATEX and/or help grade a problem set.
Homework (70%).
Weekly problem sets, with collaboration usually allowed.

Many of the problems already have solutions posted on the internet or in course bibles. No preexisting solutions may be used. Violations of this policy will be dealt with severely.

Independent Project (25%).
You will carry out independent work to exercise your new mastery of algorithms. It can have several forms, or be a combination:
Read
some new (not yet textbook) algorithms from the recent research literature, and provide an improved (of greater clarity) presentation/synthesis of the results
Research
a new algorithm that improves upon the state of the art, either for a classical problem or one that arises naturally from your own work
Implement
some interesting algorithms and study/compare their performance. Considerations include choice of algorithm, design of good tests, interpretation of results, and design and analysis of heuristics for improving performance in practice.
Collaboration (in groups of at most 3) is encouraged on these final projects.

Collaboration Policy. Collaboration is encouraged on all aspects of the class, except where explicitly forbidden. Note:
  1. All collaboration (who and what) must be clearly indicated in writing on anything turned in.
  2. Homeworks may be solved collaboratively except as explictly forbidden, but solutions must be written up independently. Groups should be small enough that each member plays a significant role.
  3. For projects every collaborator must contribute significantly to reading, implementation, and writeup. To allow this, groups should limit their size to 3 unless the project is unusually large. All members should be involved with all parts of the project and writeup.

Textbooks. There are no textbooks covering a majority portion of the material we will be studying in this class. Roughly 20% of the material is covered in Goemans' lecture notes (see below). Our lectures will often draw from the following (optional) texts, all of which we consider nice to have.
  1. Michel Goemans. Class notes for Advanced Algorithms, at http://theory.lcs.mit.edu/~goemans.
  2. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms. MIT Press. 2001.
  3. Ahuja, Magnanti, and Orlin. Network Flows. Prentice Hall, 1993.
  4. Motwani and Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  5. Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
  6. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
  7. Robert Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983. A classic--no longer up to date, but outstanding writing.
  8. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer Verlag, 2000.
  9. Dorit Hochbaum (ed.). Approximation Algorithms for NP-Hard Problems. Brooks Cole, 1996.