Text Books

There are two good texts available for this course. You can choose whichever one you prefer. At the end of the course, I'll collect feedback which will help me to choose one for use in future years. 

Sipser has been used in this course for the past several years. The course will cover topics in roughly the same order that they are presented in Sipser. It is more concise than the other text. 

Moore & Mertens is a newer text and has been an alternate choice in this course for the past few years.. I prefer the writing style in this book. I think it does a very good job of motivating and teaching the course material. It is also much longer than Sipser. It has a lot of extra material that is not covered in the course but that you may find interesting (eg. quantum computing and randomized algorithms). The material is not presented in the same order that it will be covered in the course.

The formal proofs are often spelled out more explicitly in Sipser.   If you are strong at understanding mathematical proofs, you should be able to follow the proofs in both books.  But if you struggle with proofs then you might prefer the style in Sipser.

There is some course material that is not covered in Moore & Mertens. I will distribute some pages from Sipser which cover these parts.  There is at least one thing that is not covered in Sipser, and so I will also distribute a few pages from Moore & Mertens.  (Don't worry - this is legal so long as I don't distribute too much of a book.) 

And in case it matters to you: Moore & Mertens is much cheaper than Sipser, despite being much heavier.