Stanford Design And Analysis Of Algorithms Videos

CS 473: Useful Resources

Illinois course materials

Lecture notes, slides, lab handouts, homeworks, and exams are available for several past semesters of algorithms classes at Illinois. For each class, I've listed only the most recent iteration for each instructor, but several older semesters are also available.

Jeff's algorithms stuff. Revised lecture notes will be posted on the schedule page throughout the semester.
Sariel Har-Peled's lecture notes
The old version of CS 473:
- Fall 2013 — Jeff Erickson —Includes lecture videos
- Spring 2014 — Chandra Chekuri
- Fall 2014 — Alexandra Kolla —Includes lecture videos
- Spring 2015 — Sariel Har-Peled
CS 374:
- Fall 2014 — Jeff Erickson —Includes lecture videos
- Spring 2014 — Chandra Chekuri and Lenny Pitt
- Fall 2015 — Chandra Chekuri —Includes lecture videos
The new version of CS 473:
- Spring 2015 — Jeff Erickson —Includes lecture videos
- Fall 2015 — Sariel Har-Peled

Course materials elsewhere

Sadly, it has become significantly less common for instructors to post their lecture notes/slides, homeworks, lab handouts, and so on to the open web. Most(?) instructors either lock their course materials inside walled gardens (Piazza, Moodle, Stellar, etc.) or delete them entirely when the course is over. Here are some useful exceptions.

MIT (Fall 2005, Spring 2008, Fall 2011) — 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):
- 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 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 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.

Recommended: 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 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/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. Focuses on more elementary material (taught in CS 225), with more emphasis on implementation and application than open-ended 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 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.

Programming contests

...which (at least at the advanced levels) are really algorithm design contests where you also happen to write some code.

ACM-ICPC Live Archive
An incomplete problem archive from the International Olympiad in Informatics. You can find a more complete archve at the individual contests' web sites.
Peking University Online Judge
TopCoder Algorithm competition
- Problem archive
- The importance of algorithms by lbackstrom@topcoder.
University of Valladolid Online Judge, whose problem archive includes all the ACM-ICPC stuff
Waterloo Programming Contests
A longer (but slightly outdated) list from Matei Zaharia.

Other