Resources
Course Materials
- Course materials repo. All labs, lesson plans, homeworks, exams, and quizzes, etc.
Other Books
In addition to Sipser’s Introduction to the Theory of Computation, we will use portions of the following texts. Both are available free and online at the links below.
- Jeff Erickson. Models of Computation..
- Arora and Barak (2007). Computational Complexity: A Modern Approach..
LaTeX
I am sorry to say that LaTeX is the standard for mathematical type setting and document creation—it is, it has been, and it will continue to be. I advise all students to learn LaTeX now before later. There is often no avoiding it.
LaTeX Distributions
General References
Drawing Graphs, DFAs, etc in LaTeX
Additional LaTeX Tools
- HackMD (Online Markdown + LaTeX collaborative editor)
- Latexmk (LaTeX “Make” script)
- Latexrun (command-line wrapper)
- Detexify (symbol reverse-lookup)
- latex2png (to use equations, e.g., in PowerPoint)
- Pandoc (conversion between many document formats)
Markdown
I like markdown, and so do most people. If I am in need of a markup language, I will almost always find a way to use markdown. (This site is written in markdown using Jekyll.)
Some useful links.
- Professor Osera has a great write-up here on how to use markdown.
- See markdownguide.org for another straightforward introduction.
- Github, which you will use in your career (but not this class), has its own flavor of markdown. See its formal specification and (a more friendly) guide here.
- I sometimes use Pandoc (also linked above & described by Osera) to render markdown to html, LaTeX, and pdf. Also, Pandoc is written in Haskell!
- I have heard good things about HackMD, which I believe lets you format documents in markdown with native support for LaTeX. I’ve yet to use it, but I have had students recommend it.
Other Texts and Readings (Optional)
On Programming Languages (Very, very optional)
- I am bound to talk about programming language theory during this semester. For those of you whom I manage to convince how great it is, I recommend:
- Learn you a Haskell for Great Good! for a fun introduction to (pure) functional programming in Haskell. This is the entry point for many people (myself included) interested in functional programming languages. Available free online at link provided.
- Programming Language Foundations in Agda for an excellent introduction to dependent type theory, language metatheory, and language mechanization. Available free online at link provided.
- I also recommend Verified Functional Programming in Agda, written by my advisor Aaron Stump. Not available online, but speak to me if you are interested and price is an issue.
- Types and Programming Languages is the de facto standard for all things PL. Every researcher I know has a copy. That being said, Pierce largely ignores denotational semantics in favor of operational semantics, which I find boring. For denotational semantics, I recommend Programming Language Foundations, which is also written by my advisor Aaron Stump. (So, feel free to email me if you are interested and price is an issue.)
On Technical Writing
Technical writing is hard. While you won’t have to do a ton of it in this course, it is something I encourage those of you with an interest in graduate school to take seriously. Here are some resources that have helped me a lot.
- Imagining the Reader, Ben Pierce.
- Mathematical Writing, Donald Knuth.
- The Chicago Manual of Style. I also highly recommend Garner’s Modern American Usage.
- The Elements of Style, Strunk and White. A bit outdated, and written in a time when pedagogical technique largely had to do with the form of your ruler swing. I think it is nevertheless a short and helpful read, even if just for reference of how some people think writing ought to be done.