CSCI 341 Theory of Computation

Fall 2025, with Schmid

Resources

Below is a few links to pages you might find helpful along the way.

Proof Writing

One of the prerequisites of the course is discrete math, in which you would have seen proof writing in a mathematical context. I will expect that you generally know your way around the first few proof methods (including mutual inclusion for showing two sets are equal, the pidgeonhole principle, and induction), but I won't assume mastery of these things. If you feel like the proof writing aspects of the course are moving too fast, the best thing for you to do is set up meetings with me. But a good reference for proof writing in math (the standard one) is Velleman's How to Prove It.

LaTeX

There are many resources out there for LaTeX. If you are getting started with LaTeX for the first time, then I would highly recommend Overleaf's online LaTeX documentation and editor.

The only issue with Overleaf's online editor is that you will be working with groups of more than 2 for most of the course, and the free version only allows for 2 editors per document.

Because it's (1) better practice and (2) cooler and (3) free, I recommend using Git(Lab/Hub) to manage your collaboration instead of an online editor. For reference, I compile all of my .tex using pdflatex.

If you really insist on an online editor, and you don't want to pay for Overleaf, I've searched around a bit and found these free alternatives to Overleaf:

Theory Texts

It is said that if a course is taught the same way for too many generations, open problems never get solved, because the people learning the subject never see a new angle on the subject. We are generally going to approach theory of computation in a different way than standard textbooks. But, if you would like to see other accounts of theory (and more exercises), there are several places you can look.

Top