Final exam and solutions are posted under "Final Exams" below
Grades have been emailed out.
Goals
This course is an introduction to the theory of computation, teaching:
· How to reason precisely about computation and prove mathematical theorems about its capabilities and limitations.
· Models of computation. These range from weak but useful models (such as finite-state machines) to universal models (such as Turing machines) that capture our intuitive notion of computation and allow us to reason about the capabilities of computers in a technology-independent manner.
· The intrinsic limits of computation. Computational problems that cannot be solved by any algorithm whatsoever (undecidability), and problems that are solvable but require inordinate computational resources (computational complexity).
· Formal language theory, such as the basics of grammars and parsing.
Who should take this course
This course is aimed at a broad audience:
· Students of computer science. Learn the theoretical foundations of the field and acquire skills in modeling and reasoning rigorously about computational phenomena. Many subsequent courses will refer to the material covered here.
· Students of mathematics. Acquire a new and illuminating “computational perspective” on mathematical problems. In addition, see how several important and famous problems in mathematics involve or are closely related to the theory of computation. These include Hilbert’s 10th Problem, Gödel’s Incompleteness Theorem, and the P vs. NP Question.
· Students of other quantitative subjects (physics, economics, biology,...). Learn to recognize and interpret computational intractability when it appears in your own discipline.
· Students seeking an intellectually interesting elective. See how the study of computation raises (and, in some cases, answers) philosophically interesting questions such as: Are there well-defined problems that cannot be solved automatically? Is solving a problem more difficult than verifying a solution?
Prerequisites
There is no formal prerequisite, except for some college-level course in mathematics. Some practical experience with computing may be helpful for understanding analogies with programming but is not essential for any of the actual coursework.
Meeting Place and Time
Lectures Tuesday and Thursday, 10:00-11:30, room Maxwell Dworkin G-115. Videos of lectures will be available via the course website 24-48 hours after the lectures.
Examinations
Midterm exam for CS121: Thursday, October 25. [CSCI E-207 midterm exam TBA.] Closed book. Equivalent to one problem set.
Final Exam for CS121: 3-hour exam [2 hours for CSCI E-207]. Closed book. Date TBA.
Homework Assignments
There will be eleven weekly problem sets (numbered 0-10). CS121 problem sets will be due Fridays at 1:00 PM sharp, beginning September 28. There will be a 20% lateness penalty for homeworks turned in by the following Monday at 1:00 PM sharp; no credit will be given for homework turned in after 1:00 PM Monday. [CSCI E-207 problem sets will be due Monday at 1:00PM with no late problem sets accepted. They will be submitted by email or, if necessary, by fax.] Each CS121 homework assignment has two or three “parts,” to be turned in as separate stapled sets of pages. The parts, but not individual problems, can be turned in “late” or “on time” separately. [CSCI E-207 problem sets are not divided into "parts."] Homeworks will be graded both for correctness and for clarity; graders are not required to guess the intended meaning of poorly written answers. Old graded CS121 [but not CSCI E-207] assignments can be picked up in Maxwell Dworkin 239.
Course Grading
The final examination counts 25%. Problem sets 1 through 10 and the quiz count equally, and total 75% of the final grade; but the lowest of these eleven scores will be dropped from consideration. (Thus, in effect, each problem set and the quiz counts 7.5%, except for the lowest, which doesn't count at all; and the final exam counts 3.33 times as much as the other grades.) There is no predetermined distribution of letter grades. Problem set 0 does not count for the final grade, but it covers essential mathematical background and should be viewed as mandatory for any student whose experience with mathematical proofs does not exceed the level of Math 21.
Collaboration Policy: PLEASE READ CAREFULLY!
What you turn in should be your own work; you should be able to explain it and reproduce it by yourself.
Limited collaboration in planning and thinking through solutions to homework problems is allowed (even encouraged), but no collaboration is allowed in writing up solutions. You are allowed to work with one or two other students currently taking CS121 [or, for DCE students, CSCI E-207] in discussing, brainstorming, and verbally walking through solutions to homework problems. But when you are through talking, you must write up your solutions independently and may not check them against each other. There may be no passing of homework papers between collaborators; nor is it permissible for one person simply to tell another the answer. Collaborators' names must be listed at the top of submitted homework papers.
While working on your problem sets, you may not refer to existing solutions, whether from other students, past offerings of this course, materials available on the internet, or elsewhere. All sources of ideas, including the names of any collaborators, must be listed on your homework paper.
Violation of these rules may be grounds for giving no credit for a homework paper and also for serious disciplinary action.
Sections
CS121 sections will be held weekly on Sundays and Mondays at times to be determined. Each student will be assigned to one of the sections. The purpose of sections is both to review the week's material and to provide guidance on the homework problems, so while attendance is not required, it is very strongly encouraged. Section leaders will also hold office hours on Tuesdays, Wednesdays, and Thursdays at times to be announced. [CSCI E-207 sections will be TBA. Students who are local may attend in person, and the sections will be videorecorded and posted for distance viewing, like the lectures, a day or so after they occur.]
Texts
Required text: Introduction to the Theory of Computation, by Michael Sipser, second edition, Thomson Course Technology. A complete list of errata to this book has been prepared by the author and it is recommended that you take an hour or so to enter them into your copy of the book.
Recommended texts: How to do Proofs, by Solow. Computers and Intractability: A Guide to the Theory of NP-Completeness, by Garey and Johnson. Discrete Mathematics and its Applications, by Rosen.
All of these are on reserve in Cabot and McKay Libraries.