Welcome to Theory of Computation. In this course we will study various models of computation leading to a characterization of the kinds of problems that can and cannot be solved by a computer, and for those problems that can be solved, a means of classifying them with respect to how difficult they are to solve. Mike Fischer has said the following about theory: "...it should establish a framework for cataloging knowledge and provide insight into general phenomena. The methods for accomplishing these goals are generality, rigor, and abstraction which allows the theoretician to throw away excess baggage in the form of irrelevant detail. If the theoretician makes the right abstractions, he can draw conclusions that are rigorous, widely applicable, and still relevant to the practical problems which were his starting point. Of course the trap in theory is abstracting the wrong parts of the problem; the results then are uninteresting because they are no longer relevant. The theoretician is like a scout looking over new territory; he travels light, and can explore a wider area than a system builder who must always keep in mind the work of implementation."
Each week, reading and about 8 problems will be assigned. You should work on all of the problems but hand in written, near-'publication quality' solutions to 4 of the problems at the beginning of the Wednesday session. Sometimes I will specify certain problems that must be part of what you hand in. All students should be prepared to discuss the reading and solutions to any of the problems. Always do all parts of a problem unless I specify otherwise. I do not object to your talking about the problems or working together, but the assumption is that each solution is independently arrived at unless noted otherwise by the solver. So, if you work with others, make sure you tell me. All students will be assumed to be able to solve all problems by the Saturday of the week they are due. If you do not understand a problem, it is your job to ask for clarification, a discussion, or a solution.
Cells phones are to be turned off for the duration of class. No vibrating! No text messaging!
Check the course Web site
http://www.cs.swarthmore.edu/~cfk/cs46
several times per week for assignments.
Required text: Elements of the Theory of Computation (second Edition) by Lewis and Papadimitriou
Homework 1 (due W, Jan. 21)
Homework 2 (due F, Jan. 23)
Homework 3 (due M, Jan. 26)
Homework 4 (due W, Jan. 28)
Homework 5 (due F, Jan. 30)
Homework 6 (due M, Feb. 2)
Homework 7 (due W, Feb. 4)
Homework 8 (due F, Feb. 6)
Homework 9 (due M, Feb. 9)
Homework 10 (due W, Feb. 11)
Homework 11 (due F, Feb. 13)
Homework 12 (due M, Feb. 16)
Homework 13 (due W, Feb. 18)
Homework 14 (due F, Feb. 20)
Homework 15 (due M, Feb. 23)
Homework 16 (due W, Feb. 25)
Homework 17 (due F, Feb. 27)
Homework 18 (due M, March 2)
Homework 19 (due W, March 4)
Homework 20 (due F, March 6)
Homework 21 (due M, March 16)
Homework 22 (due W, March 18)
Homework 23 (due F, March 20)
Homework 24 (due M, March 23)
Homework 25 (due W, March 25)
Homework 26 (due F, March 27)
Homework 27 (due M, March 30)
Homework 28 (due W, April 1)
Homework 29 (due F, April 3)
Homework 30 (due M, April 6)
Homework 31 (due W, April 8)
Homework 32 (due F, April 10)
Homework 33 (due M, April 13)
Homework 34 (due W, April 15)
Homework 35 (due F, April 17)
Homework 36 (due M, April 20)
Homework 37 (due W, April 22)
Homework 38 (due F, April 24)
Homework 39 (due M, April 27)
Homework 40 (due W, April 29)
Homework 41 (due F, May 1)
Closed book, closed notes Comprehensive Final Exam
Friday, 8 May 9am-12n in Sci 264.
Written homework will generally be due by the beginning of class on Wednesdays. Late homework will be penalized (severity will depend on lateness and what we have done in class). Even if you miss a deadline, you are strongly encouraged to complete the assignment anyway, since this really is the only effective way to learn the material.