Office: Maxwell Dworkin 237

CS121 staff email: cs121@seas.harvard.edu
CSCI E-121 staff email: cscie121@seas.harvard.edu

Lectures Tuesdays and Thursdays from 10:00 to 11:30AM in Maxwell Dworkin G115

Why This Course Has Two Numbers

CS 121 is an undergraduate course in Harvard College. CSCI E-121 is a course offered through the Harvard Extension School for undergraduate or graduate credit. CSCI E-121 is a distance only course. The lectures are the same as those for CS121, and are viewed by video. CS121 and CSCI E-121 have similar homework and exam schedules but different homework assignments and exams.

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. The basics of grammars and parsing.

You may want to look at last year's exams (links below) to get an idea of what you will learn in this course.

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

CS 121 expects students to have "experience in formal mathematics at the level of CS 20". This means that we will assume prior exposure to reading and writing mathematical proofs (including proofs by induction) and working with mathematical concepts such as sets, functions, relations, and graphs. This material will be reviewed in sections during shopping week and with Problem Set 0, both of which should be considered essential for anyone with limited experience in mathematical proofs. Students who have taken or are taking Math 23 or Math 25 are prepared for this course. We (Professor Lewis and the TFs) are also happy to discuss your preparation during office hours and help bring you up to speed.

Course Grading

The final examination counts 25%. Each of the problem sets other than PS0 and the midterm exam count equally, and total 75% of the final grade, but the lowest of these scores will be dropped. There is no predetermined distribution of letter grades. PS0 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 is limited. 

Reading

The required textbook for the course is Introduction to the Theory of Computation by Michael Sipser (3rd edition). (The 2nd edition can also be used, though page numbers will differ.) Every lecture will have assigned reading, which you are expected to do before coming to class. We will set up a mechanism for you to provide feedback on the reading before class, so that lecture can focus on the difficult points. The author has maintained a list of errata at http://math.mit.edu/~sipser/book.html, which you are encouraged to enter into your book right away to avoid future confusions.

For more mathematical background (in addition to Chapter 0 in Sipser), we recommend the materials from CS20, and/or the books How to Do Proofs by Solow, and Discrete Mathematics and its Applications by Rosen. Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson is recommended for "culture" and as a good reference for practicing computer scientists.

Homework Assignments

There will be weekly problem sets. CS121 homeworks will generally be due on Tuesdays at 11:59pm sharp. There will be a 20% lateness penalty for CS121 homeworks turned in by Friday at 11:59pm sharp; no credit will be given for homework turned in after 11:59 Friday. CSCI E-121 problem sets are generally due Fridays at 11:59pm, with no late problem sets accepted.

Each CS121 homework assignment has 2-3 “parts”, to be turned in electronically as separate documents. The parts, but not individual problems, can be turned in “late” or “on time” separately. CSCI E-121 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.

You should learn the LaTeX document processing system and use it when preparing your solutions. It is the standard text processing tool of mathematical scientists everywhere, and it is free and noncommercial. To minimize the LaTeX learning curve for newbies, we provide the problem sets as LaTeX source code and you can just type in the answers without mastering a lot of the document formatting features.

The first problem set (PS0) doesn't count, but it will be graded and returned as though it did. Its purpose is to review essential mathematical background and to get everyone used to the document preparation and submission procedures and to the style in which the rest of the problem sets will be graded.

Collaboration Policy: PLEASE READ CAREFULLY!

We strongly suggest you attempt each problem on your own before talking it over with your friends, classmates, or the course staff. We nonetheless encourage students to collaborate in small groups (2-4 people in CS 121, 2-3 in CSCI E-121) on homework. Small study groups can be a big help in mastering course material, and also be fun and a good way to make friends. But students must write up solutions on their own, neither copying solutions nor providing solutions to be copied. What you turn in should be your own work product; you should be able to explain and reproduce it.

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. If a source beyond the course materials is used in a solution ––for example, an "expert" consultant other than the course staff, or another text ––there must be a proper scholarly citation of the source.

All collaborators must be identified. Each problem set turned in must include a collaboration statement:

"I worked alone and only with course materials"

or

"I collaborated on this assignment with <students in class>, 
got help from <people other than collaborators and course staff>, 
and referred to <citations to sources other than the class material from this term>".

No problem set will be given credit until it has a collaboration statement.

Violation of these rules may be grounds for giving no credit for a homework paper and also for serious disciplinary action.

Examinations

Midterm: 90-minute exam. Closed book. Thursday, October 17.
Final Exam for CS121: 3-hour exam. Closed book.
Final exam for CSCI E-121: 2-hour exam. Closed book. 

CSCI E-121 students who cannot come to Cambridge will need to make arrangements to take the exams at an appropriate testing center. The Extension School will be in touch with you about these arrangements.

Here are a previous CS121 midterm and CSCI E-121 midterm.
Here are a previous CS121 final and CSCI E-121 final.

Using LaTeX

Using LaTeX makes it easier to modify your answers without rewriting, and it makes it far easier for us to read what you wrote, so you'll never lose points for illegibility. We will supply a template for each problem set solution so you will have to do a minimum of formatting other than typing your answers. To use LaTeX, you'll need to install it--there are versions available for all major operating systems--see here. Or else you can useScribTex, a Web-based interface to LaTeX that requires no download.

Once you've done that, you can download the LaTeX source for the problem set you're working on to get the problem definitions, and just add your answers. You'll also need the cs121 class file: cs121.cls. (CSCI E-121 students will find the corresponding files on a separate page.) You can either put the class file in the directory where the problem set .tex file is, or add it to your TEXINPUTS path: on OS X or Linux, use something like:

setenv TEXINPUTS ":$HOME/files/tex"  

• It's possible to produce figures with LaTeX, but for our purposes it probably isn't worth the trouble: instead, just scan in pictures and include them.
• Don't worry too much about formatting--it's possible to spend hours getting things to look "just so", but that isn't necessary for problem sets. The contents of your writing and explanations is far more important than the exact layout.
• If you're trying to figure out how to display something in LaTeX, just google it--there's likely an answer somewhere on the web. Also try the documentation.