CS 373: Introduction to Theory of Computation
Fall 2013
Lectures for this class are on Tuesdays and Thursdays. Lecture meets from 12:30 - 1:45 in 1320 DCL. Fifty minute discussion sections meet on Tuesdays at 2, and 3, and Wednesdays at 12, 1, and 4 in 1214 Siebel.
You are expected to attend lectures and discussion sections. If you cannot be there, you must arrange to pick up any handouts or returned homeworks you may have missed, e.g. by coming to office hours.
Some handouts may be hardcopy and some virtual. Virtual handouts will available on the lectures web page.
Announcements, homework hints, etc will be posted Piazza. You must check Piazza regularly (at least once a day). Only particularly important announcements will be duplicated on the course home page. You are encouraged to use Piazza to initiate and participate in discussion related to the class. However, students should not post solutions or hints to homework problems.
There is no required textbook this semester. If you would like to own a textbook, then Introduction to the Theory of Computation Michel Sipser 3rd Ed., PWS Publishing Company, 2012, would be the most useful. Check out its errata page, which contains a few substantive (as opposed to stylistic) errors.
There are only modest differences between the second and third editions. If you are on a tight budget, a used copy of the second edition should work ok.
Other books you may find useful are:
These texts are on reserve in the Grainger Library.
In previous terms the software package JFLAP was used. This package allows you to experiment with the various automata that we will learn in this course. This term we will not be teaching or using it officially.
Using JFLAP to help solve homework problems or check your solutions is not cheating, unless we explicitly tell you otherwise. However, you should make sure you also end up learning how to work these problems by hand, because you'll need to be able to do this on quizzes and exams.