Algorithms, Etc.

by Jeff Erickson
January 2015 revision

This page contains lecture notes and other course materials for various algorithms classes I have taught at the University of Illinois, Urbana-Champaign. The notes are numbered in the order I cover the material in a typical undergraduate class, wtih notes on more advanced material (indicated by the symbol ♥) intersprsed appropriately.

New Jan 2015: In addition to the algorithms notes I have been maintaining since 1999, this page also contains new notes on "Models of Computation", which cover a small subset of the material normally taught in undergraduate courses in formal languages and automata. I wrote these notes for a new junior-level course on "Algorithms and Models of Computation" that Lenny Pitt and I developed, which is now required for all undergraduate computer science and computer engineering majors at UIUC. You can see this material in context at my Fall 2014 course web site.

Each lecture note includes several exercises, and a near-complete archive of my old homeworks, exams, and discussion problems also follows the lecture notes on this page. Please do not ask me for solutions to the exercises. I will say no, even if you're an instructor.

You are welcome to use any subset of this material in your own classes without asking my permission, but please give me proper credit and please include a link to this web page (http://www.cs.illinois.edu/~jeffe/teaching/algorithms) for the most recent revision.

Feedback is always welcome, especially bug reports. I particularly appreciate hearing from students or instructors outside UIUC who find this stuff useful (or useless). More information about this material is available at the bottom of this page.

Creative Commons License
Algorithms and Models of Computation by Jeff Erickson are licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Everything

Algorithms Notes

Models of Computation Notes

  1. Cover pages
  2. Strings
  3. Regular languages
  4. Finite-state automata
  5. Nondeterministic automata
  6. Context-free languages
  7. Turing machings
  8. Universal models
  9. Undecidability
  10. Nondeterministic Turing machines

Homeworks, Exams, and Labs

More Information

Copyright. Except as indicated otherwise, all material linked from this web page is Copyright © 1999–2014 Jeff Erickson. Anyone may freely download, print, copy, and/or distribute anything on this page, either electronically or on paper. However, nothing on this page may be sold in any form for more than the actual cost of reproduction or distribution. For example, you are welcome to maintain local copies on your own web server, but you are not allowed to require an access fee (such as tuition) to view your local copy; that's the same as selling it. If you distribute these notes, please give me proper credit and please include a link to this web page (http://www.cs.illinois.edu/~jeffe/teaching/algorithms). If you're a lawyer, read the legalese.

Teaching assistants. I am deeply indebted to my fantastic teaching assistants, without whom running effective courses would be utterly impossible. In particular, these TAs contributed a significant fraction of the homework and discussion problems.

Aditya Ramani, Akash Gautam, Alex Steiger, Alina Ene, Amir Nayyeri, Asha Seetharam, Ashish Vulimiri, Ben Moseley, Brad Sturt, Brian Ensink, Chao Xu, Chris Neihengen, Connor Clark, Dan Bullok, Dan Cranston, Daniel Khashabi, David Morrison, Johnathon Fischer, Junqing Deng, Ekta Manaktala, Erin Wolf Chambers, Gail Steitz, Gio Kao, Grant Czajkowski, Hsien-Chih Chang, Igor Gammer, John Lee, Kent Quanrud, Kevin Milans, Kevin Small, Kyle Fox, Kyle Jao, Lan Chen, Michael Bond, Mitch Harris, Naveen Arivazhagen, Nick Bachmair, Nick Hurlburt, Nirman Kumar, Nitish Korula, Rachit Agarwal, Reza Zamani-Nasab, Rishi Talreja, Rob McCann, Shripad Thite, Subhro Roy, Tana Wattanawaroon, and Yasu Furakawa.
Please see the cover material for additional acknowledgements.

Previous versions. The 2009, 2011, and 2013 editions of this material are still available; these include a few "retired" notes on material I have not taught for several years. More recent revisions are probably available on the official web site of whatever course I'm teaching this semester.

Caveat Lector. Some of these lecture notes have been used less often than others and are therefore (sometimes considerably) less complete/polished. In particular, the models of computation notes have been used at most once, and thus are best viewed as incomplete preliminary drafts. I offer extra credit to my own students for finding bugs in the notes, and I strongly encourage anyone else using them to do the same. Please send me bug reports. Also, each of these notes contains significantly more than one lecture's worth of material. In a typical 75-minute lecture, I tend to cover 3–5 pages of material—a bit more if I'm lecturing to graduate students than to undergraduates. I realize this makes the label "lecture notes" rather inaccurate.

Am I writing a textbook? No. All textbooks suck.

Well, okay, fine, go ahead and call this a textbook if you like.

No doubt this statement will be followed by an annotated list of all textbooks, and why each one is crap.
— Adam Contini, MetaFilter, January 4, 2010

Jeff Erickson — 30 Dec 2014