CS/Math 4631 - Theory of Computation - 2015

Instructor: Dr. R. Rosebrugh, Dunn 203

General Information

The course meeting time is 13:30-14:20MWF in Dunn 104. Assistance is available other times by appointment; contact the instructor by email. For official detail see the Academic Calendar. 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 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 February 18. The final examination will be two hours long (but you will have three hours to write it.)

Grades

The final grade will be based on the assignments and quizzes, the mid-term test, and a final examination. The weights will be approximately 20%, 20% and 60% respectively.

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 be present for 75% of quizzes (from assigned homework);
and you must submit 75% of short assignments.

Assignments

There will be one-question short assignments at least twice a week to be handed in and taken up at the next class. There will be several longer written assignments, every two to three weeks. Late assignments not 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 (but preferably use one of the many available packages). A tutorial will be provided. Be sure to attempt all problems in the text, not just the ones assigned to be handed in.

Assignment 1

Chapter 1: 1.4 a,c,e (specify the simpler DFA's with tables); 1.6 a,b,c,f; 1.8 a) (but use the algorithm from Thm 1.25), 1.31
Due in class: January 19

Please attempt the other text problems.