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.
- 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.
Course Notes for CSCB38/236/240 - Introduction to the theory of computation by Vassos Hadzilacos. Excellent coverage of regular langauges and expressions, DFAs and NFAs, and context-free langagues and grammars. Also includes an excellent review of induction, especially for proving correctness of algorithms.
Fall 2011) — notes, videos, and problem sets
— homeworks, occasional slides
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):
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.
- 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.
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).
- 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?)
- Programming contests
- ...which (at least at the advanced levels) are really algorithm design contests where you also happen to write some code.
We'll add more links here as we discover them. Suggestions are welcome!