CS/Math 4631 - Theory of Computation - 2016

General Information

The course meeting time is 11:30-12:20MWF in HH 218. Assistance is available other times by appointment; contact the instructor by email. For official detail see the Academic Calendar. Please check this URL regularly for information about the course.

Texts

The textbook is Introduction to the Theory of Computation, 3rd Edition by by Michael Sipser. (The link is to Amazon, also try AbeBooks).

Also recommended is the free on-line textbook: Introduction to Theory of Computation by Anil Maheshwari Michiel Smid.

A different and valuable perspective from Jim Lambek is freely available at http://www.math.mcgill.ca/barr/papers/pga.pdf

You can and should find many resources about Theory of Computation elsewhere on the web.

Syllabus

We will cover Chapters 1-5 and parts of 6, 7 and 9 in Sipser's book. There will be written assignments, in-class quizzes (based on assigned homework), a midterm test, and a final exam.

Test/Exam

The midterm test will be held in class on October 24. The final examination will be two hours long (but you will have three hours to write it.)

Grades

Note: In order to pass the course:

you must obtain a passing mark on the aggregate of the test and the final;
and you must submit at least 80% of short assignments.

The final grade will be based on the assignments, the mid-term test, and a final examination. Grades will be normally assigned using approximately the following weights: 20%, 20% and 60% respectively.

Assignments

There will be (one or two question) short assignments two or three times a week, usually from the textbook. They will be handed in and taken up at the next class. Therefore, late assignments cannot be accepted.

All assignments are an essential part of the course. All written work handed in must be typeset using LaTeX. The exception is that you may hand draw diagrams (though there are many available packages). A LaTeX tutorial (with source code) will be provided. Be sure to attempt all problems in the text, not just the ones assigned to be handed in.