CS/ECE 374A fa24: 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 course materials. Revised lecture notes will be posted on the schedule page throughout the semester.
• Sariel Har-Peled's algorithms notes
• CS 374:
  • Fall 2014 — Jeff Erickson — Includes lecture videos
  • Spring 2014 —  Chandra Chekuri and Lenny Pitt
  • Fall 2015 —  Chandra Chekuri — Includes lecture videos
• CS 473:
  • Spring 2015 — Jeff Erickson — Includes lecture videos
  • Fall 2015 — Sariel Har-Peled
  • Spring 2016 — Jeff Erickson — Includes lecture videos
• 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

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.

• Toronto: 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.
• MIT (Fall 2005, Spring 2008, Fall 2011) — notes, videos, and problem sets
• 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, 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.
• 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.
• Course Notes for CSCB38/236/240 - Introduction to the theory of computation by Vassos Hadzilacos. Excellent review of induction, especially for the proof of correctness of algorithms; also excellent coverage of regular langauges and expressions, DFAs and NFAs, and context-free langagues and grammars.
• 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

Other stuff:

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

• Computer Science StackExchange
• How to ace 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