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.