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

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

I have now posted the now complete set of typed notes, that is the notes for Lectures 1 to 12 and the tutorial by Brendan Lucier on mechanism design.

I am providing a link to a draft of a new text on approximation algorithms by David Shmoys and David Williamson .

I added a link to notes by Shuchi Chawla to the list (below) of relevant course notes. I just added the the url for the spring 2007 course CS 880. There are other course notes by Shuchi Chawla that are equally relevant. I provided the CS 880 course link as I used lectures 12 and 13 in preparing. An excellent source for gaining an appreciation of the primal dual approach is the overview paper by David Williamson .

Please send any comments or questions to the instructor:
This course is a new 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: randomized algorithms and Markov chains, LP and SDP relaxations, primal dual algorithms, online primal dual algorithms, multi commodity flows, embedding techniques, data stream 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: 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

Lecture Notes will be 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

    • Problem Sets
  • Problem set 1
  • Problem set 2
  • Problem set 3

    • Other Handouts will be posted here.

  • Paper concerning sum (multi) coloring referring to k-clawfree graphs.
  • Here is the article by Khanna et al which is needed for question 4 of assignment 2.
  • 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 .