George Mason University 

DEPARTMENT OF COMPUTER SCIENCE

CS600 - Theory of Computation - Fall 2009


M -- 4:30-7:10, Sci & Tech I,  224


Prerequisites | Description | Readings | Syllabus | Grading | Late | TA | Dates

This page last updated on 8/27/2009


Professor Dana Richards 

703-993-1545 

richards@gmu.edu

(Please prefix the subject of your email with CS600.) 


Course office hours: Tuesday and Thursday 11:00-12:00 or by appt.

Engineering Bldg  425 



PREREQUISITES : 


CS583 (and so CS310, CS330, and MATH 125); that is data structures, algorithms, undergraduate theory, and discrete math.


DESCRIPTION : 


(From catalog)  Introduction to logic and proof techniques, formal languages, automata theory, and computational complexity. Specific topics include regular and context-free languages, Turing machines, NP-completeness, and undecidabilty.


READINGS: 


  1. Intro to the Theory of Computation--second edition, by Sipser.
  2. Logic in Computer Science--second edition, by Huth and Ryan.


SYLLABUS: 


The pace will vary and some chapters will be abridged.


Chapter 0 -- Sipser

Chapter 1 -- Sipser

Chapter 2 -- Sipser

Chapter 3 -- Sipser

Chapter 4 -- Sipser

Chapter 5 -- Sipser

Chapter 6 -- Sipser

Chapter 7 -- Sipser

Chapter 8 -- Sipser (?)

Chapter 1 -- Huth and Ryan

Chapter 2 -- Huth and Ryan


Tentatively, Exam #1 will be October 19  and Exam #2 will be December 14 (at 4:30). 


GRADING : 


Exams -- 100%


The two exams, including the final, each cover about a half of the semester; the final is not cumulative. 

Of these exams the highest score will count 60%, and the lowest 40%. 


Homework is ungraded.


All testing is closed book, but limited notes are permitted, as follows for exams. One sheet of notes (8.5 by 11 inches, 1 side only). NO COPYING is allowed. That means no photocopying of anything, even the textbook, though you may write out material from it verbatim. It also means no copying of anyone else's notes, even by hand. You may use a computer for editing your own notes. The sheet must be turned in with your exam. Violations of these rules for creating the notes is considered a violation of the Honor Code. 


TA:  none


No laptops, etc. (If you need a laptop for note-taking then sit up front.)