Computer Science 142 and Mathematics 167
Theory of Computation
Syllabus, Fall 2001

Professor: Ran (``RON'') Libeskind-Hadas
Office: Olin 1245
Office Hours: To be determined

Phone: x18976
E-mail: hadas@cs.hmc.edu
Course Homepage: http://www.cs.hmc.edu/courses/2001/fall/cs142

Meeting Times: Monday, Wednesday, Friday, 10-10:50 AM
Meeting Place: Galileo Edwards

Graders: Rob Adams, Matt Brubeck, Kurt Dresner, Peter Henry, Chris Lundberg, Katie Ray

What Is This Course About?

This course addresses some of the fundamental mathematical ideas underlying computer science. The ultimate goal of the course is to address the question: "What are the fundamental capabilities and limitations of a computer?" We address this question by studying three related areas of theoretical computer science: automata theory, computability theory, and complexity theory.

Automata theory examines the question "what is a computer?" and "what can it do?" We examine three fundamental mathematical models of computation (finite automata, pushdown automata, and Turing machines) and study their capabilities and limitations. We're also able to show that many other possible models of computation are in fact equivalent to one of our three fundamental models.

Computability theory is a natural extension of automata theory. It examines the question "what is the most powerful model of computation?" and "what can it do?" The answers turn out to be very surprising!

Complexity theory addresses the question "how long does it take to solve a particular problem?" (or more generally, "how much of my favorite resource does it take to solve a particular problem?" where the resource could be time, memory, etc.) We study several complexity classes such as P, NP, and PSPACE among others and develop some interesting results that relate these classes to one another.

In addition to the theoretical component, we investigate applications of this material to compilers, computer architecture, and robotics.

Is This Course for You?

The prerequisites for this course are CS 60 and Math 55. Off-campus students are strongly encouraged to have completed either Math 55 at Harvey Mudd or Math 103 (Combinatorics) at Pomona prior to enrolling in this course.

The homeworks and exams in this course emphasize proofs. We use elementary set theory (countability and uncountability arguments), induction, discrete functions, and graph theory very frequently. There will be a few assignments that require programming. You may use your favorite high-level programming language (which is defined formally to be an element of {C, C++, Java, Pascal, SML}) for these assignments.

Text

Introduction to the Theory of Computation, by Michael Sipser. First Edition. PWS Publishing Company.

Assignments and Grades

There will be an assignment every week except for the weeks of the exams. Problem sets will be distributed on Wednesday and due the following Wednesday at 5 PM in the box outside Ran's office door. In addition, you are entitled to two extensions until Friday at 5 PM that you may use anytime during the semester. There is no need to request advance permission to use the extensions. No late submissions will be accepted after using these extensions.

There will be two exams during the term. There will be a comprehensive final exam at the end of the term.

Finally, there will be in-class worksheets given in most lectures. These will be short exercises based on the material being covered in class. You will be given a few minutes to work on these exercises in class and will turn in your solution at the end of the lecture. These submissions will not be graded or returned. You will get full credit for a worksheet simply by turning it in and showing that you made an effort to solve the given problems. The point breakdown is as follows: 
 
	Problem Sets: 40 %
	Exams: 25 %
	Final Exam: 25 %
	In-class Worksheets:  10 %

Collaboration Policy

Collaboration on homeworks is encouraged. This means that you may discuss approaches to solving a problem with any classmate or member of the course staff. At the top of every problem set you should list the people with whom you discussed any of the problems.

Copying any part of a solution from any source is strictly disallowed. All students are expected to conduct themselves in accordance with the Harvey Mudd Honor Code. If you have any questions about what is appropriate or inappropriate collaboration, please talk to Ran. No collaboration is allowed on the exams.