6.854/18.415J: Advanced Algorithms (Fall 2020) Course Information

Instructor: David Karger, 32-G592. karger@mit.edu. http://people.csail.mit.edu/karger/

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

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. This course is designed to be a capstone course in algorithms that surveys some of the most powerful algorithmic techniques and key computational models. We will cover a broad selection of topics including amortization, hashing, dimensionality reduction, bit scaling, network flow, linear programing, and approximation algorithms. Domains that we will explore include data structures; algorithmic graph theory; streaming algorithms; online algorithms; parallel algorithms; computational geometry; external memory/cache oblivious algorithms; and continuous optimization.

Online Class Experimentation

This semester's pandemic has forced us into purely online teaching. In an effort to make lemons from lemonade, I plan to experiment with a variety of different approaches to teaching and grading in order to determine what works best. Among experiments I'm already considering are: I will be developing other experiments on the fly.

Goals

We hope that this class will confer

Content:

The goal is to be broad rather than deep. This list is approximate.

Prerequisites:

Strong performance in an undergraduate class in algorithms (e.g., 6.046/18.410), discrete mathematics and probability (6.042 is more than sufficient), and substantial mathematical maturity.

Requirements:

Homework/Collaboration Policy.

  1. Homework is due Wednesdays at the beginning of class. We'll have boxes or piles for dropping them off at the back of the room. Those boxes will be collected a few minutes in, and homework arriving after will be considered late.
  2. Each student has a total budget of 15 “slack” points to accommodate his/her late problem submissions. So, for example, if there is a problem set with a total of five problems on it, submitting three of these problems on time, one of them before Friday class, and one of them before Monday class will consume three slack points in total.
  3. Write each subproblem (each separately labeled part) on a separate sheet of paper and include your name and email address. Also, make sure your name appears on each page.
  4. Collaboration is encouraged, except where explicitly forbidden.
  5. You may not seek out answers from other sources without prior permission. In particular, you may not use bibles or posted solutions to problems from previous years.
  6. Each student is required to grade (at least) one problem in the semester. We will have a TA-supervised grading session each week. This session is used to make sure that the graders fully understand the solution, while they can grade the problems at home after this session.
  7. For questions about grading, please contact the graders (emails listed on the website) first. Once you reach an agreement, the grader should send an email to the grading supervisor with a short explanation and a new grade.
  8. All late psets should be sent electronically to the TA supervising the grading.

Textbooks.

There are no textbooks covering a majority of the material we will be studying. Lectures will often draw from the following (optional) texts, all of which are nice to have.
  1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms. MIT Press. 2001.
  2. Ahuja, Magnanti, and Orlin. Network Flows. Prentice Hall, 1993.
  3. Motwani and Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  4. Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
  5. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
  6. Robert Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1983. A classic—no longer up to date, but outstanding writing.
  7. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer Verlag, 2000.
  8. Williamson and Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.