CS 473: Useful Resources

Notes, slides, etc.

Lecture notes, slides, homeworks, and exams from algorithms classes at UIUC and several other universities can be found on the web:

At UIUC:
- Jeff's algorithms stuff: lecture notes, homeworks, and exams from 12 semesters of CS 473 and CS 573. Revised lecture notes will be posted on the schedule page throughout the semester.
- Chandra Chekuri (CS 473, Fall 2009)
- Sariel Har-Peled (CS 473G = CS 573, Fall 2003 and Fall 2007)
- Mahesh Viswanathan (CS 473, Spring 2008).
Elsewhere:
- MIT (Spring 2008; Fall 2005, with video and alternate notes)
- CMU (Fall 2008, Fall 2009, Spring 2010, Fall 2010, and Fall 2011)
- University of Washington (several semesters)

And now I understand the problems you can see.

Videos

Videos of algorithms lectures from several universities can be found on the web. See especially the following:

Jeff's CS 473 lectures from Spring 2010 — Sorry, only accessible from on-campus or with a University NetID.
MIT's Introduction to Algorithms, taught by Erik Demaine and Charles Leiserson
IIT Kanpur's Computer Algorithms 2, taught by Shashank Mehta (unfortunately not indexed by topic)
Berkeley's CS 61B: Data Structures (roughly equivalent to our CS 225), taught by Jonathan Shewchuk
Algorithms courses from UC Davis (on iTunes):
- Algorithm Design and Analysis (undergraduate), taught by Dan Gusfield
- Design and Analysis of Algorithms (graduate), taught by Charles Martel

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 open-ended design than CS 473.

Algorithms: Design and Analysis taught by Tim Roughgarden, loosely based on algorithms classes at Stanford
- Part 1 (March–April 2012 and June-July 2012)
- Part 2 (October–November 2012)
Algorithms, taught by Robert Sedgwick and Kevin Wayne, loosely based on algorithms classes at Princeton
- Part 1 (August–September 2012)
- Part 2 (November–December 2012)
Algorithms, taught by Michael Littman, loosely based on algorithms classes at Rutgers (June–August 2012)
Intro to Theoretical Computer Science, taught by Sebastian Wernicke (October-December 2012)

Textbooks

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. I've asked Grainger Library to put copies of all these books on reserve.

Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGraw-Hill, 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 CS 473.
Algorithm Design by Jon Kleinberg and Éva Tardos (Addison-Wesley, 2005). Based on algorithms classes at Cornell. This is the standard recommended textbook for CS 573.
Introduction to Algorithms (3rd edition) 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. A significant fraction of this book has been transcribed into Wikipedia.
Algorithms (5th edition) by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011). Based on algorithms classes at Princeton. This book doesn't cover everything in CS 473, but what it does cover it covers well; older editions are also fine. A crippled electronic version is available through the University library.

Review

For review of prerequisite material, we strongly recommend the following online resources. (This stuff is also covered in several dead-tree textbooks, but really, why bother?)

Building Blocks for Theoretical Computer Science by Margaret Fleck, written specifically for CS 173.
Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer, written for the Mathematics for Computer Science course at MIT.
Open Data Structures by Pat Morin, an open-content textbook (like open source, but for words) that really ought to be the standard reference for CS 225.

Other

We'll add more links here as we discover them. Suggestions welcome!