P2 CSC2420 Home Page

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


This page will provide WWW access to various documents concerning CSC2420. Announcements will also be made on this page. The class will be held Mondays 12-2 in BA 3116.


Please send any comments or questions to the instructor:

Announcements will be placed here as appopriate.

Assignment 3.s been graded and most of you have reccieved the graded assignment back bu email. If not I should have it in my office by Thursday, May 4. I also have everyones graded Assignment 2. I can also tell you the grade I am submitting.

I have the graded assignments and I am in most of the week (except Wednesday). Email me if you want to be sure I am in.


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. Other possible topics include: online algorithms (adversarial and stochastic models), the random order online model, derandomizing online algorithms, submodular maximization, LP and SDP relaxations, primal dual algorithms, sublinear time algorithms, parameterized complexity, fine grained complexity, data stream algorithms, MapReduce algorithms, multiplicative weights algorithms, spectral methods, 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:

  • 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.
  • Lecture 1 Motivating the course and starting to introduce basic combinatorial paradigms. Online algorithms, greedy, partial enumeration greedy
  • Lecture 2 Continuing to introduce basic combinatorial paradigms. Greedy, priority model, dynamic programming
  • Lecture 3 Continuing to introduce basic combinatorial paradigms. Dynamic programming, oblivious and non-oblivious local search, max flow and Ford Fulkerson
  • Lecture 4 Continue Ford Fulkerson, applications of max flow, IP/LP rounding, unrelated machines makespan problem.
  • Lecture 5 Some recent progress on restricted machines makespan, LP duality (primal dual analysis and dual fitting), begin randomization.
  • Lecture 6 Continue randomized algorithms, derandomization
  • Lecture 7 was given by Lalla Mouatadid and there were no slides. I am posting below a set of lecture notes on FPT, and Virginia Williams' survey on fine-grained complexity.
  • Lecture 8 Proofs of the KVV result, further discussion of online bipartite matching algorithms and extension, random walks and Sch\"{o}ning's $k$-SAT algorithm.
  • Lecture 9 Sublinear time algorithms, property testing, streaming algorithms.
  • Lecture 10 Streaming algorithms for frequently occuring and unique elements, relation of streaming to some other models, primality testing, the constructive Lov\'{a}sz Local Lemma.
  • Lecture 11 MapReduce; Spectral algorithms and spectral graph theory
  • Lecture 12 Maximizing a set function subject to a cardinality constraint; new areas of algorithmic interest (game theory/mechanism design, fair division).

  • Assignments will be posted here. Note questions for P1 will be incrementally added as the relevant material is presented. The due date will be set once we have have sufficiently many approriate questions. But I advise working on questions as soon as the relevant material has been introduced.
  • Assignment 1
  • Assignment 2
  • Assignment 3

  • Additioinal papers/slides will be posted here.
  • 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
  • Dan Spielman's tutorial on spectral graph theory