Instructor:   Gerry Howser (Gerry.Howser{at}mst{dot}edu) Computer Science Building, Room 314 (easy as pi)

Textbook (required): Sipser, M. Introduction to the Theory of Computation, 2nd Edition, Thomson Course Technology, 2006.

Automation Tool: JFLAP 7.1 (available by downloading from and installing on your own machine or M: drive)
You should have Java 1.6 to run this program. (If you are using a Mac, see the note under JFLAP news on the JFLAP website.)

You can find other references in the class bibliography.

Assignments, class notes, grades, and other material will be made available on the course homepage on Canvas. Students are responsible for checking this resource frequently. Site

Course Overview:

In this course we address the following foundational question of computer science: what can be (efficiently) automated? To even understand this question, we must be clear about what we mean by automation. So we begin the course by looking at several different mathematical models of computation: finite state machines, pushdown automata, and Turing machines.

A comparison of the various models of computation will suggest that Turing machines accurately represent our intuitive notion of computation, i.e. the problems that can be solved by a Turing machine are exactly those problems that can be solved automatically. As a result we rephrase our question: what problems can be solved by a Turing machine? We will look at some examples of problems that can be solved by Turing machines and examples of problems that cannot. Along the way we will also see ways to show that a problem cannot be solved automatically.

Finally we will consider the question of efficiency. Different ways of solving the same problem may take different amounts of time or space. We will talk about ways to analyze and compare the efficiency of algorithms, and then use this to classify problems according to how efficiently they can be solved. We will see examples of problems that can be solved efficiently, examples of problems that cannot be solved efficiently, and examples of problems for which the existence of efficient solutions is an enigma.

Intended Course Schedule:

Automata and Languages
Weeks 1 - 2: introduction; finite state machines; regular languages
Weeks 3 - 4: pushdown automata; context-free languages; Exam 1
Weeks 5 - 6: Turing machines; the Church-Turing thesis; decidability; reducibility
Weeks 7 - 8: time complexity (P and NP); Exam 2
Week 9: time complexity (NP-completeness)
Week 10: intractibility
Exam Week: Final Exam

Attendance and Participation:

Regular attendance and participation is expected of all students and will affect your grade. Active participation in this class means coming to class on time, completing assigned reading and exercises, presenting exercises, listening to others, contributing ideas of your own, and asking questions as they come up.

Assignments, Collaboration, and the Honor System:

This course operates in accordance with the principles of the Kalamazoo College Honor System: responsibility for personal behavior, independent thought, respect for others, and environmental responsibility. In particular, academic integrity is a fundamental principle of scholarship. Representing someone else's work as your own, in any form, constitutes academic dishonesty. Unauthorized collaboration and receiving help from others outside the bounds permitted by the instructor are also violations of the College honor code. You are responsible for working within the permitted bounds, and acknowledging any help from others or contributions from other sources.

Reading assignments and related exercises will be assigned for each class. You are expected to come to class having completed the assignment and being prepared to discuss both the ideas from the reading and your solutions to the exercises. You are encouraged to work on these exercises in groups; just be sure that each group member understands each answer well enough to present it to the class. When presenting an answer, you should acknowledge any help that you received.

Homework assignments will be assigned throughout the semester. Homework assignments are due at the beginning of class on the designated due date. Late assignments will not be accepted, except under special circumstances with my advance permission.

If you get stuck on a homework problem or just want to see if you are heading in the right direction, I am quite willing to help you. You may also discuss the requirements, concepts, and overall strategies related to homework problems with your classmates, as long as you walk away from the discussion without notes. It is important that you write up your homework solutions individually, acknowledging any ideas from others that you have used. Organizing and writing up the solutions on your own ensures that you really understand the solution. Copying someone else's solution does not help you learn the material. Submitting a copied solution as your own work is plagiarism.

The course will also involve two examinations and a final examination. Obviously your answers to exam questions should be entirely your own work and not the result of collaboration with others. If the use of outside sources (such as the textbook) is permitted, be careful to cite ideas and material from those sources, whether derived, summarized, quoted or paraphrased.

Penalties for violating the Honor Code in this course may include receiving no credit for an assignment, a lowered course grade, or failure of the course. Depending on the severity of the incident, a report may be sent to the Dean's Office, which may result in additional consequences, including suspension from the College. Any subsequent violation will result in the immediate failure of this course.