CS 573 Graduate Algorithms, Fall 2011


CS 573 is a broad introduction to algorithms aimed at graduate students in computer science and related areas, including students in the MCS and 5-year BS/MS programs. Mathematically/algorithmically mature undergraduates and graduate students in other departments are also welcome to register, but please come talk to me first. Most undergraduates should take CS 473 instead.

Students are assumed to have mastered the material taught in CS 173 (discrete mathematics) and CS 225 (basic algorithms and data structures). We emphasize that "mastery" is not the same as "exposure" or even "a good grade"; hence, Homework Zero. Programming experience is helpful; a strong mathematics background is even more helpful. We also assume a level of mathematical, algorithmic, and general intellectual maturity consistent with admission to a top-5 graduate program in computer science.

Course grades are based on homeworks (25% total), two midterms (22.5% each), and a final exam (30%). There will be several opportunities for extra credit, which will be applied after the curve. All homework and exam grades will be posted on Compass Gradebook ('My Grades' under 'My Tools'). See the grading policies for more details.

Reading material:
There is no required textbook. Pointers to existing lecture notes from various sources will be posted to the course web site as the semester progresses. We will primarily rely on notes from the following sources:

For students who prefer an actual dead-tree reference, we recommend the following textbooks. The campus bookstore probably doesn't have them, but they're cheaper online anyway. Grainger Library has copies of all these books on reserve.

  • Algorithm Design by Jon Kleinberg and √Čva Tardos (Addison-Wesley, 2005). Based on algorithms classes at Cornell.
  • Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGraw-Hill, 2006). Based on the undergraduate algorithms course at Berkeley; a complete PDF draft of the book is available online.
  • Introduction to Algorithms by Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein (MIT Press/McGraw-Hill, 2009). Based on algorithms classes at MIT. The first and second editions are also fine.

Finally, as a review of important mathematical prerequisites, we recommend Eric Lehman and Tom Leighton's extensive lecture notes for the Mathematics for Computer Science course at MIT.

Newsgroup: class.cs573 on the news server news.cs.uiuc.edu
Please read the newsgroup at least once a day. Important announcements will be posted both on this web site and on the newsgroup. You must sign up for access if you have not already done so.