CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Spring 2019)


This page will provide WWW access to various documents concerning CSC2420. Announcements will also be made on this page.

NOTE: I have had a couple of requests for an extension with regard to the last assignment. I am willing to do this but I have to get grades in for undergraduate students and Chris is away next week. So, I will grant an extension for the last assignment until Thursday, April 11. All assignments should be submitted electronically to me and with a copy to Chris (ckar at cs.toronto.edu). If you want to submit this Thursday that will faciliate our grading. You can revise any "early" submissions up to the due date. THE TOPIC REVIEW IS STILL DUE THIS THURSDAY, APRIL 4. Presentations are scheduled for this Thursday. If you intend to use slides (which is probably a good idea), then please send me a file that I can upload to save time.

NOTE: I discussed the nature of the reading project assignment. Namely, you are asked to write a survey type paper on a topic relevant to this course. For example, as I mentioned, you could take any of the chapters mentioned in the index of the online text draft and help develop the material in that chapter. In some cases, even a section within a chapter is a topic of substantial interest. But you are not restricted to these topics. I think everyone by now has a project. The presentation next week will make up a small part (say 10%) of the grade for the project with 90% based on the writen project.

I have now posted all the questions for the final assignment.


Please send any comments or questions to the instructor:

Announcements will be placed here as appopriate.


This course serves as a foundational course, appropriate for students in computer science, computer engineering, and mathematics. However, the course should also be of interest to ``theory students'' looking for research topics. We will begin with topics usually discussed in undergraduate courses such as our CSC373/CSC375 using some less standard examples and also discussing some precise models for standard algorithmic paradigms such as greedy, local search and dynamic programming algorithms. This term there will be an emphasis on online, online-like algorithms and ``beyod wirst case analysis". Some possible topics include: stochastic models, the random order online model, derandomizing online algorithms, submodular maximization, primal dual algorithms, sublinear time algorithms, parameterized complexity, fine grained complexity, data stream algorithms, multiplicative weights algorithms, algorithmic aspects of mechanism design,

We will not use any one text book for this course. There are a number of excellent undergraduate texts (e.g. "Algorithm Design" by Jon Kleinberg and Eva Tardos; "Introduction to Algorithms" by Corman, Leiserson, Rivest and Stein; ``Algorithmics: Theory and Practice" by Brassard and Bratley; and "Algorithms" by DsGupta, Papadimitriou and U. Vazirani) that cover the standard topics and include some advanced material. There are also a number of texts on somewhat specialized topics (e.g. "Approximation Algorithms" by V. Vazirani; "A First Course in Combinatorial Optimization", by James Lee; and "Randomized Algorithms" by Motwani and Raghaven). There are also many web accessible courses that indicate the diversity of topics taught in graduate algorithms courses. For example, you may want to consider the following sources:

  • Tom Roughgarden Stanford Lectures
  • Princeton University CS521
  • University of Washington CSE 521
  • University of Washington CSE 522
  • Cornell University CSC6820
  • CMU 451/651
  • Nikhil Devanur Online Course
  • Avner Magen LP and SDP Course

  • Lecture slides will be posted here.
  • Week 1 Motivating the course and starting to introduce basic combinatorial paradigms. Online algorithms, greedy, partial enumeration greedy
  • Week 2 The priority model for greedy and myopic algorithms, inapproximations in the priority framework. Interval selection. Charging arguments. Some extensions of the online and priority models. Set packing and s-set packing.
  • Week 3 Set packing continued. (s+1)-claw free graphs. The job interval scheduling problem. Approximation algorithms for set cover and vertex cover. Priority algorithms with revocable acceptances and priority stack algorithms. Chordal graphs, perfect elimination orderings, k-PEOs and inductive k-independent graphs.
  • Week 4 Chris' slides for online learning
  • Week 5 Local search. Oblivious and non-oblivious local search for exact max-k-sat, local seacrh for k-claw free graphs, matroids and indepoendence systems, maximizing modular and submodular functions subject to a matroid constraint.
  • Week 6 Finish oblivious and non-oblivious local search for maximizing monotone submodular functions subject to a matroid constraint. Randomized algorithms and in particular online randomized algortithms.
  • Week 7 The Yannakakis randomized rounding algorithm for max-sat. The Buchbinder et al deterministic and randomized ``double-sided online algorithms'' for the unconstrained (non-monotone) submodluar maximization (USM) problem. The adaption to max-sat and the Poloczek et al presentation of the randomized online max-sat algorithm. (See also chapters of online text draft.)
  • Week 8. There are no lecture slides for this week. Chris gave a blackboard lecture dicussing the ADWORDS problem and the DISPATCH paper. I am posting the Mehta survey article (which discusses the ADWORDS problem) and the DISPATCH paper.
  • Week 9 Proof sketch for 1/2 competitive ratio of the randomized double-sided greedy algorithm for the USM problem. The corespondence between the USM result and the 3/4 randomized algorithm for max-sat. Brief discussion of primal dual algorithms and primal dual based analysis. Start of discussion of stochstic input models.
  • Week 10 More discussion on ROM model. Random walk algorithm for 2-sat and k-sat. Start of sublinear time algorithms.
  • Week 11 Sublinear time algorithms, often conceptually very simple but deceptively hard to analyze. Streamng algorithms.

  • Assignments will be posted here.

    The due date for A1 was February 25, the last day to drop a graduate course without penalty.

    Assignment 2 is the reading project on a topic of your choice.

    I have now posted all questions for the final assignment. The due date is April 4, the last class of the term.

  • Assignment 1
  • Final Assignment

  • Additional papers/slides will be posted here.
  • Probability Primer
  • Kim Larsen slides
  • The FPT slides by Daniel Marx: Marx Lecture 1 ; Marx Lecture 2 ; Marx Lecture 3 ; Marx Lecture 4
  • Here is Virginia Williams fine-grained complexity
  • Here is the Khanna et al paper concerning local search algorithms for exact max-k-sat.
  • The seminal KVV paper regarding online bipartite matching and the Ranking algorithm.
  • The 2013 survey by Aranyak Mehta concerning Online Matching and Adllocation. This is an excellent survey but of course not totally up to date. Mehta survey.
  • The Chang et al DISPATCH algorithm paper for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals. DISPATCH algorithm.
  • Here are 2009 Lecture Notes on Data Stream Algorithms by Amit Chakrabarti. He has more recent 2011 and 2015 courses on Data Stream Algorithms. Data Stream Lecture Notes

  • Preliminary versions of some chapters from our new ``Online Algorithms'' text will be posted here. We are just beginning this text so there are bound to be mistakes and incomplete references. We welcome any comments.
  • Here is a draft (posted March 14) of our index and Chapters 1-4 and 7,8 but missing most references and historical notes. And as noted before, all of the chapters are still being written. Chapters 1,2,3,4,7,8
  • Here is a draft of the current bibliography for some chapters. Even for chapters where we have some references, the history is far from comoplete. Current bibliography.