"CS 374": Useful Resources

Course material

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 n semesters of CS 473 and CS 573. Revised lecture notes will be posted on the schedule page throughout the semester.
  • Sariel Har-Peled's lecture notes
  • Past iterations of CS 374:
    • Spring 2015 - Chandra Chekuri and Lenny Pitt
    • Fall 2014 - Jeff Erikcson
    • Spring 2014 - Jeff Erikcson and Lenny Pitt
  • Past iterations of CS 373:
    • Spring 2014 - Jose Meseguer
    • Fall 2013 - Mahesh Viswanathan
    • Spring 2013 - Mahesh Viswanathan
    • Fall 2012 - Mahesh Viswanathan
  • Past iterations of CS 473:
    • Spring 2010 — Jeff Erickson — Includes lecture videos
    • Fall 2010 — Chandra Chekuri
    • Spring 2011 — Sariel Har-Peled
    • Fall 2011 — Sariel Har-Peled
    • Spring 2012 — Chandra Chekuri
    • Fall 2012 — Jeff Erickson — Includes some lecture videos
    • Spring 2013 — Sariel Har-Peled and Alexandra Kolla
    • Spring 2014 — Chandra Chekuri
• 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)

Rewritten by machine and new technology,
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 Bombay's Design and Analysis of Algorithms, taught by Abhiram Ranade
• 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 (July-August 2013)
  • Part 2 (September–October 2013)
• Algorithms, taught by Robert Sedgwick and Kevin Wayne, loosely based on algorithms classes at Princeton
  • Part 1 (August–September 2013)
  • Part 2 (November–December 2013)
• Analysis of Algorithms, taught by Robert Sedgwick, loosely based on a more advanced class at Princeton.
• Algorithms, taught by Michael Littman, loosely based on algorithms classes at Rutgers (self-paced)
• Intro to Theoretical Computer Science, taught by Sebastian Wernicke (self-paced)
• 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: 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.

Programming contests

...which (at least at the top levels) are really algorithm design contests where you also some code, I guess.

• ACM-ICPC Live Archive
• An incomplete problem archive from the International Olympiad in Informatics. You can find more recent problems 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

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

• Algorithm is not a four-letter word by Jamis Buck
• Computer Science StackExchange
• How to rock an algorithms interview, by Kevin Simler at Palantir
• Reddit: Algorithms
• Where can I find difficult algorithm/data structure problems? at Quora
• Wikipedia: Computer Science portal