P2 CSC2420 Home Page

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

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

Please send any comments or questions to the instructor:
Announcements

Assignment 3 has been graded and you can pick up your assignment from me SF 2302B). I am in this week and away next week. If you just want to know your grade on the assignment you can email me.

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 normally 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, the random order model, derandomizing online algorithms, submodular maximization, LP and SDP relaxations, primal dual algorithms, sublinear time algorithms, data stream algorithms, MapReduce algorithms, multiplicative weights algorithms, spectral methods, algorithmic aspects of mechanism design, social networks and information retrieval.

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 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
  • Lecture 2
  • Lecture 3
  • Lecture 4
  • Lecture 5
  • Lecture 6
  • Lecture 7
  • Lecture 9
  • Lecture 10
  • Lecture 11
  • Lecture 12

    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.
  • Assignment 1
  • Assignment 2
  • Assignment 3

    • Additional references and papers will be posted here.

  • 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 .
  • A survey by Mehta on Online Matching and Ad Allocation
  • Lecture Notes by Muthukrishnan on Streaming
  • A survey by Arora et al on the Weighted Majority paradigm
  • Dan Spielman's tutorial on spectral graph theory