CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Fall 2012)


This page will provide WWW access to various documents concerning CSC2420. Announcements will also be made on this page. Please send any comments or questions to the instructor:


Announcements for week of December 3. and December 10. I have now posted the complete assignment three having 5 questions (with an open problem BONUS question). The assignment is due Friday, December 14 at 5PM the latest. Please drop off your assignment any time before that in Robert's office SF 4301. You can also email the assignment to Rabert; the email is ``robere..at..cs.toronto.edu''

There will be a TA office hour Monday, December 10 at 1PM in SF 3207.

My CSC 200 office hours are 3-4 on Tuesdays so I will definitely be in my office then and will usually be there 4-5 or later. I am usually in my office and you can drop by at any time or email me for a definite appointment.


This course is a relatively new (first taught, fall 2010 and then spring 2012) graduate level introduction to the design and analysis of algorithms. The course will serve as a foundational course, appropriate for students in computer science, computer engineering, and mathematics. We will begin with topics normally discussed in undergraduate courses such as our CSC373/CSC37 using some less standard examples and also discussing some precise models for standard algorithmic paradigms such as greedy, local search and dynamic programming algorithms. Other possible topics include: matroids and other independence systems, submodular function maximization, randomized algorithms, Markov chains, LP and SDP relaxations, primal dual algorithms, online algorithms, random order model, embedding techniques, data stream algorithms, multiplicative weights algorithms, spectral and other algebraic methods, algorithmic aspects of mechanism design and social networks.

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 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 is also a text "Computer Science Thoery for the Information Age" in preparation by Hopcroft and Kannan on Geometric and Spectral Methods (with applications to problems having high dimensional and/or massive data). There are also many web accessible courses that indicate the diversity of topics taught in graduate algorithms courses. ncluding very crude notes I used in the spring 2012 course). For example, you may want to consider the following sources:

http://www.cs.toronto.edu/~bor/2420f11, http://www.cs.washington.edu/education/courses/521, http://www.cs.washington.edu/education/courses/522, http://math.mit.edu/~goemans/18433.html, http://stellar.mit.edu/S/course/18/fa08/18.415/index.html, http://www.cs.cornell.edu/courses/cs6820/2009fa/, http://www.cs.cmu.edu/~avrim/451f09/index.html. http://pages.cs.wisc.edu/~shuchi/courses/880-S07/#lect


Assignments will be posted here.


  • Assignment 1

  • Assignment 2

  • Assignment 3
  • Lecture slides will be posted here. I will not generally do proofs in these slides but rather do them in class.
  • Lecture 1
  • Lecture 2
  • Lecture 3
  • Lecture 4
  • Lecture 5
  • Lecture 6
  • Lecture 7
  • Lecture 8
  • Lecture 9
  • Lecture 10
  • Lecture 11
  • Lecture 12

  • Lecture Notes from the Fall 2010 course are posted here.
  • Lecture 1
  • Lecture 2
  • Lecture 3
  • Lecture 4
  • Lecture 5
  • Lecture 6
  • Lecture 7
  • Lecture 8
  • Lecture 9
  • Lecture 10
  • Lecture 11
  • Lecture 12
  • Tutorial on Mechanism Design
  • Other Handouts from Fall, 2010 course are posted here.

  • Paper concerning sum (multi) coloring referring to k-clawfree graphs.
  • Here is the article by Khanna et al which uses non oblivious local search to improve the local search approximation for Max-k-Sat.
  • Here is the article by Calinescu et al (see pages 26-28) that gives the approximation bound for the standard greedy algorithm for maximizing a submodular set function in a k-independent set system .
  • Here is the article by Buchbinder et al that provides the deterministic 1/3 and randomized 1/2 approximation for the unconstrained maximization of a submodular set function .