Computer Science 142
Computational Complexity Theory (a.k.a. "Theocomp")
Syllabus, Spring 2005

Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1245
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: Monday, Tuesday, Wednesday 4:15-5:15 and Friday 3:15-5:15
Course Time and Location: Mondays and Wednesdays, 2:45-4 PM, in Jacobs B134
Course Assistant: Tim Carnes

Course Homepage: www.cs.hmc.edu/courses/2005/spring/cs142

What Is This Course About?

This is officially a course on computational complexity theory, the study of the "hardness" of computational problems. In addition, the course has a small component on computabilty theory.

The course is divided into two parts: Part 1 of the course will be lecture-based and will cover the foundations of computability and complexity. In Part 2 of the course, you will select a topic related to this course, give a presentation to the rest of the class on your topic, and assign and grade homework problems on your presentation.

Part 1 of the course will begin with a review of basic concepts from computability theory (the material taught in the last part of CS 81), augmented with some more advanced material on this topic. The remainder of Part 1 will be dedicated to computational complexity theory. Here is a tentative list of topics:

Computability Theory

Computational Complexity Theory

Part 2 of the course will comprise student presentations of material related to this course. The objective of this part of the course is to develop the ability to read original research papers and present the material clearly in class. You will work with Ran in advance to select the topic, find the appropriate papers to read, and develop your in-class presentation. In addition, you will be asked to assign approximately 2 homework problems on your topic and you will grade these problems. These homeworks scores will count as required regular homework for your classmates.

Texts

There is no textbook for the course. Lectures will be self-contained. Some books will be placed on reserve in the library and this will be announced in class.

Attendance and Participation

On-time attendance in every class is absolutely required to pass the course. If you are sick or have a special reason for missing class, please contact Ran before the class that you will miss. Otherwise, you are expected to be in class. Please make sure to arrive on-time as a courtesy to the instructor and your classmates. Participation in class is also expected and is a component of the course grade.

Assignments

There will be two assignments each week. On Mondays, you will receive a short assignment typically comprising 1 or 2 problems and worth approximately 20-25 points. This assignment is due on Wednesday at the beginning of class. On Wednesday, you will receive a longer assignment typically comprising 3-5 problems and worth approximately 75-80 points. This assignment is due on the following Monday at the beginning of class. All problem set submissions must be typeset, preferably using LaTeX. Assignments will be posted in both pdf and LaTeX source formats on the course web page.

Exams

There will be two take-home exams in this course. The first exam will be on the material in Part 1 of the course and will take place shortly after spring break. The second exam will cover the material presented in Part 2 of the course and will take place near the end of the semester. There will be no final exam.

Grades

The components of the course are worth the following: 
 
	Homework in Parts 1 and 2 of the course: 60% 
	Take-home Exam 1:  15%
	Take-home Exam 2:  10%
	Part 2 presentation:  15%
Note that attendance is not factored into this breakdown, but is required in order to pass the course.

Collaboration Policy

Collaboration on homeworks is encouraged. This means that you may discuss approaches to solving a problem with anyone in the class. On each submitted homework, please indicate the names of all people with whom you discussed your solutions. Unless indicated otherwise, no written sources (other than your own notes) should be consulted in solving homework problems. There should be no collaboration on the takehome exams. All parties, including off-campus students, are expected to follow the Harvey Mudd Honor code.