Lectures: Mondays and Wednesdays, 12:00 - 1:15pm, Room 105 Sanders Physics

Instructor: Professor Nancy Ide

Office: 104.6 Sanders Physics

Phone: (845) 437-5988

Email: ide [at] cs.vassar.edu

Office Hours: Mondays and Wednesdays 11am - 12pm and by appointment

This course introduces students to the theory of computation, the mathematical foundation of computer science. We will consider what is an appropriate mathematical model of a computer, what types of computations are possible in the model, what types are not, the inherent complexity of certain computations, etc. Although considering computers as abstract mathematical objects may on the surface seem unrelated to “real” computing, in fact many concepts you will encounter are fundamental to important areas of computer science, including compiler design, hardware design, object-oriented design, computational linguistics, and even the syntax of the UNIX grep and awk commands.

During the course, you will gain an understanding of the intimate connection between computation and language recognition. We will study several classes of abstract machine including finite automata, push-down automata and Turing machines, along with several classes of languages such as regular and context-free languages. In addition we will look at problems like the Halting Problem that are not amenable to a computer solution.

The course provides essential background for CMPU331, Compiler Design: ideally, you should take CMPU331 in the semester immediately following completion of this course. It is also a good foundation for CMPU366, Computational Linguistics.

• Syllabus
• Schedule, readings, lecture notes, assignments and solutions
• Optional programming assignments
• How to succeed in this course
• CS240 Discussion List (google group)
• JFlap automaton drawing software
• xkcd