These are lecture notes that I wrote for the course “Algorithms and Models of Computation” at the University of Illinois, Urbana-Champaign for the first time in Fall 2014. This course is a broad introduction to theoretical computer science, aimed at third-year computer science and computer engineering majors, that covers both fundamental topics in algorithms, for which I already have copious notes, and fundamental topics on formal languages and automata, for which I wrote the notes you are reading now.

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).

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 very new—Lenny Pitt and I developed the course and offered the first pilot in Spring 2014 (with Lenny presenting the formal language material) — so even the choice of which material to emphasize, sketch, or exclude is still very much in flux.