CSC 341  Grinnell College  Spring, 2009 
Automata, Formal Languages, and Computational Complexity  
Assignments  Schedule ( .dvi format / pdf format / postscript )  
Instructor  Textbooks  Course Work  Deadlines  Collaboration  Grading 
This course explores the logical and mathematical foundations of computer science by exploring the following topics in some depth:
Models of Computation: finite and pushdown automata; nondeterminism; recursive functions; regular expressions
Chomsky Language Hierarchy: regular languages, contextfree languages, Turingdecidable (recursive) languages, Turingrecognizable (recursive enumerable) languages, contextsensitive languages
Solvable and Unsolvable Problems: Turing machines; Church's thesis and universal Turing machines; the halting problem; unsolvability
P and NP Complexity Classes the classes P and NP; NPcomplete problems; intractable problems; approximate, nonoptimal solutions to NP problems
Topics related to space complexity, intractability, approximation and probabilistic algorithms, and publickey encryption will be included as time permits.
While some applications may be discussed from time to time, this course will emphasize the formal underpinnings and theory of computer science.
Office: Science 3811
Telephone: extension 4208
Email: walker@cs.grinnell.edu
Office hours are posted weekly on the bulletin board outside Science 3811, with additional hours possible by appointment. You may reserve a half hour meeting by signing up on the weekly schedule, but please sign up at least a day in advance.
Michael Sipser, Introduction to the Theory of Computation, Second Edition, Thomson/Course Technology, 2006, ISBN: 13: 9760534950972 and 10: 0534950973.
Additional Resources: Numerous online materials allow users to simulate various models of formal machines. Here are a few examples:
While the schedule for this course is expected to evolve, a Tentative Class Schedule is available in .dvi , pdf, and postscript formats.
Also, if you are logged into the departmental network and want a copy printed, click duerer to have a copy printed on the printer duerer .
This course will involve written assignments, oral presentations, and tests.
Written Assignments: Exercises will be assigned regularly throughout the course.
Oral Presentations: The subject of the theory of computation includes the classification of numerous classical problems. During the semester, students (working in groups) will present at least two of these problems, together with an outline of their classification.
Hour Tests: Following the Tentative Class Schedule (.dvi format / pdf / postscript), hour tests are scheduled for Monday, February 9 for Wednesday, March 4, and for Monday, April 27.
Exam: Following the published exam schedule, an exam is scheduled for 9:00 am on Tuesday, May 12, during exam week.
Late Work will not be accepted, as it interferes with normal grading and with preparation for other parts of this course. As homework may be handwritten, exceptions will not be granted for computer system malfunctions.
Exception: Allowances may be made for students with special circumstances, subject to written verification by the Health Center or the Student Affairs Office.
Collaboration often will be allowed on problems from the textbook, but collaboration normally will NOT be allowed on supplemental problems and tests. To avoid confusion, the rules for collaboration on homework are included in the specification of each assignment.
This instructor's grading philosophy dictates that the final grade should ultimately be based upon each student's demonstration of her or his understanding of the material, not on the performance of the class as a whole nor on a strict percentile basis. The following scheme is proposed as a base for how the various assignments and tests will be counted in the final grade.
Written Assignments:  46% 
Oral Presenations:  10% 
Hour Tests:  24% 
Exam:  20% 
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/341.sp09/index.shtml
created 4 January 2008 last revised 29 January 2009 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 