Computer Science 125: Algorithms & Complexity

SYLLABUS

Staff | Objectives | Audience | Prereqs | FAQ | Grading | Collaboration | Texts | Topics

 

Course website: http://seas.harvard.edu/~cs125/index.html
Course Piazza site: https://piazza.com/class/hzfxvafcvxt4gx

Lectures: Tuesday & Thursday 10-11:30, Maxwell Dworkin G-125

Course Staff

Prof. Michael Mitzenmacher (Maxwell Dworkin 331)
Prof. Salil Vadhan (Maxwell Dworkin 337)

TFs: Alex Makelov, Joy Zheng

See Piazza for office hours, and to send questions to the course staff.

Objectives

This course is an introduction to theoretical computer science, teaching:

Who should take this course

The material in this course should be of interest to a wide range of students:

• Students of computer science. Learn the theoretical foundations of the field, acquire a toolkit of useful algorithmic techniques, and develop 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,...). Acquire a toolkit of algorithmic techniques that can be applied to computational problems arising in your discipline, and learn to recognize when inherent intractability may a barrier to solving such problems.

• 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?

At the same time, CS 125 is an intensive course meant only for students with strong mathematical preparation and interest in engaging deeply with the material. For the vast majority of students, the combination of CS 121 and 124 will remain the most appropriate option for learning this material.

Prerequisites

Students in CS 125 should have comfort with reading and writing mathematical proofs, at the level of Math 25 or 55 (which may be taken concurrently), as well as the ability to pick up new mathematical concepts on one's own as required. We are expecting most of the students to be upperclassmen who have taken Math 25 or 55 (or other rigorous mathematics courses) before, but freshmen are also welcome provided they have sufficient comfort with rigorous mathematics. Students from concentrations other than computer science and mathematics are very welcome, provided again that they meet the prerequisites.

While most of the work in the course will be theoretical, there will be some assignments that involve programming. Students should also be able to program in a high-level programming language, such as C, C++, Java or OCaml.  Extensive programming experience is not required;  the level of a student having taken CS50 or having similar programming experience in high school would be sufficient.

Frequently Asked Questions

Since this is a new couerse, there are a number of common questions being asked about it.

Grading

All assignments will be due at 5pm on the day due;  generally assignments will be due on “non-class days” (typically Wednesday or Friday) to avoid sleep-deprived class attendance.  Assignments will be accepted late for medical emergencies or similar exceptional circumstances;  it is strongly preferred that such circumstances be discussed in advance when possible.  Late assignments must be OK’ed by Professor Mitzenmacher or Professor Vadhan.   

Please remember it is better to turn in an incomplete assignment rather than no assignment; indeed, we expect that most students will not solve some of the problems we assign. All assignments should be turned in electronically, as pdf or text files. You should have a scanner available, or be familiar with LaTeX, or otherwise be ready to deal with turning in pdfs of mathematical work. (LaTeX is highly, highly recommended)


Approximate grading breakdown:

Collaboration Policy

For problem sets, limited collaboration in planning and thinking through solutions to homework problems is allowed, but no collaboration is allowed in writing up solutions. You are allowed to work with a few other students currently taking CS 125 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.

If you collaborate with other students in the course in the planning and design of solutions to homework problems, then you should specify their names on your homework papers.

For the programming assignments, you may work in pairs. It is assumed you will not work with anyone besides your partner.

Under no circumstances may you use solution sets to problems that may have been distributed by the course in past years, or the homework papers of students who have taken the course past years. Nor should you look up solution sets from other similar courses. All sources of ideas other than the course lectures and section (including collaborators, textbooks, Wikipedia, etc.) should be explicitly credited on your homework papers.

Violation of these rules may be grounds for giving no credit for a homework paper and also for serious disciplinary action. Severe punishments will apply, so please do not violate these rules. If you have any questions about these rules, please ask an instructor.

Recommended Texts

While there is no required text, the following books may be useful:

We will make lecture notes available within a few days of each lecture.

Tentative List of Topics