CS 473: Administrivia
About This Course
 Audience:

CS 473 (officially "CS 498 DL1") is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines.
 Prerequisites:

CS 374 or equivalent, or graduate standing. In particular,
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.
 Coursework:

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 Moodle. See the grading policies for more details.
 Am I in the right place?

Well, that depends.
 If you are an undergraduate who has taken CS 374, you are in the right place! Welcome!
 If you are an undergraduate who has not taken CS 374 or an equivalent course, you are in the wrong place. You really do need to take CS 374 first.
 If you are a graduate student in computer science or a related discipline, you are in the right place! Welcome! In particular:
 If you are a CS PhD student whose program of study includes "CS 573", you are in the right place.
 Yes, even if you've already taken an undergraduatelevel algorithms class.
 If you are a graduate student without an undergraduate background in computer science, you might still be in the right place. Welcome! Past experience suggests that a strong background in proofbased mathematics is more important for success in this class than programming experience. If you have any concerns, please talk to Chandra or Ruta as soon as possible.
 Finally, if you want an easy A, you are probably in the wrong place.
 Postrequisites

This course replaces CS 573 as a prerequisite for all 500level algorithms courses, in particular:
 Degree Requirements

This course is not specifically required for any program on campus, but it has been approved to satisfy requirements in each of the following programs:
However, this course does not count toward the requirement in all graduate programs for 500level credits. It's a 400level course.
Class Resources
 Moodle
 We will use Moodle for grades. If you were registered for the course at the start of the semester, you should already have access to our Moodle site; if not, contact one of the instructors.
 Gradescope
 We will use Gradescope for homework submission and grading. Anyone can sign up for access to the CS 473 Gradescope site with their favorite alias and email address, using the selfenrollment code 9E2PZM. We will separately ask you for your alias, so that we can map your homework grades to you.
 Piazza
 We will use Piazza for online discussions. Anyone can sign up for access with their favorite email address. We strongly encourage posting questions on any courserelated topic to Piazza rather than emailing the course staff. You can even post your questions anonymously. (However, we can only give you extra credit for helpful posts if you post them using your real name.)
 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.
 Illinois Course Materials

 Course materials elsewhere


MIT
(Fall 2005,
Spring 2008,
Fall 2011,
Spring 2015) — notes, videos, and problem sets
 Berkeley
(Spring 2009,
Fall 2014)
— homeworks, occasional slides
 CMU
(Spring 2013,
Fall 2013,
Spring 2014,
Fall 2014,
Spring 2015) — notes/slides only
 Stanford (Summer 2013) — slides and problem sets
 Washington (several quarters) — notes/slides, sporadic problem sets
 UC Davis (videos on iTunes):
 MOOCs

Both Coursera and Udacity are offering complete algorithms courses, with videos, readings, and automatically graded exercises. By necessity, these courses tend to focus more on implementation and less on proofs and openended design than CS 374 or 473. I have included only MOOCs with videos that are always freely available.
 Algorithms: Design and Analysis Part 1 and Part 2, taught by Tim Roughgarden, loosely based on algorithms classes at Stanford.
 Algorithms, taught by Michael Littman, loosely based on algorithms classes at Rutgers
 Intro to Theoretical Computer Science, taught by Sebastian Wernicke
 Algorithms, compiled by Bhanu Kapoor. Included for completeness, but good only for review of the most basic material.
 Textbooks
 For students who prefer an actual deadtree 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.

Recommended:
Algorithm Design by Jon Kleinberg and Éva Tardos (AddisonWesley, 2005). Based on algorithms classes at Cornell.
 Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGrawHill, 2006). Based on the undergraduate algorithms course at Berkeley. A complete draft of the book is available online. This is the closest traditionally published approximation to the old CS 473 and the algorithms portion of CS 374.
 Introduction to Algorithms (3rd edition) by Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein (MIT Press/McGrawHill, 2009). Based on algorithms classes at MIT. The first and second editions are also fine. A significant fraction of this book has been transcribed into Wikipedia.
 Algorithms (5th edition) by Robert Sedgewick and Kevin Wayne (AddisonWesley, 2011). Based on algorithms classes at Princeton. Focuses on more elementary material (taught in CS 225), with more emphasis on implementation and application than openended design and analysis. A crippled electronic version is available through the University library (sorry, only for Illinois folks).
 Review
 For review of prerequisite material, we strongly recommend the following online resources. (This stuff is also covered in several deadtree textbooks, but really, why bother?)