Models of Computation
Jeff Erickson

December 28, 2018

http://jeffe.cs.illinois.edu/teaching/algorithms/

© Copyright 2014–2019 Jeff Erickson. Last update December 28, 2018.

This work may be freely copied and distributed in any medium.
It may not be sold for more than the actual cost of reproduction, storage, or transmittal.
This work is available under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
For license details, see http://creativecommons.org/licenses/by-nc-sa/4.0/.
For the most recent edition, see http://jeffe.cs.illinois.edu/teaching/algorithms/.

I’m writing a book.
I’ve got the page numbers done,
so now I just have to fill in the rest.
— Stephen Wright

About These Notes
These are lecture notes that I wrote for a new course “Algorithms and Models of Computation”
at the University of Illinois, Urbana-Champaign in Fall 2014 and revised again in Fall 2016. Thiscourse is a broad introduction to theoretical computer science, aimed at third-year computerscience and computer engineering majors, that covers both fundamental topics in algorithms, forwhich I already have copious notes, and fundamental topics on formal languages and automata,for which I wrote the notes you are reading now.
The most recent revision of these notes (or nearly so) is available online at http://jeffe.cs.
illinois.edu/teaching/algorithms/, along with my algorithms notes and a near-complete archiveof past homeworks and exams from all my theoretical computer science classes. I plan to revise
and reorganize these whenever I teach this material, so you may find more recent versions on
the web page of whatever course I am currently teaching.

About the Exercises
Each note ends with several exercises, many of which I used in homeworks, discussion sections,or exams. ? Stars indicate more challenging problems (which I have not used in homeworks,
discussion sections, or exams). Many of these exercises were contributed by my amazing teachingassistants:
Alex Steiger, Chao Xu, Charlie Carlson, Connor Clark, Gail Steitz, Grant Czajkowski, HsienChih Chang, Jacob Laurel, Junqing Deng, Konstantinos Koiliaris, Mark Idleman, NickBachmair, Patrick Lin, Phillip Shih, Sahand Mozaffari, Shalan Naqvi, Spencer Gordon, Srihita
Vatsavaya, Tana Wattanawaroon Umang Mathur, Vipul Goyal, and Yipu Wang.

Please do not ask me for solutions to the exercises. If you are a student, seeing the solution
will rob you of the experience of solving the problem yourself, which is the only way to learn thematerial. If you are an instructor, you shouldn’t ask your students to solve problems that youcan’t solve yourself. (I don’t always follow my own advice, so I’m sure some of the problems arebuggy.)

Caveat Lector!
These notes are best viewed as an unfinished first draft. You should assume the notes
contain several major errors, in addition to the usual unending supply of typos, fencepost errors,
off-by-one errors, and brain farts. Before Fall 2014, I had not taught this material in more than
two decades. Moreover, the course itself is still relatively new, so even the choice of whichmaterial to emphasize, sketch, or exclude is still in flux.
I would sincerely appreciate feedback of any kind, especially bug reports.
Thanks, and enjoy!
— Jeff