Computer Science 125: Algorithms & Complexity


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


Course website:
Course Piazza site:
or try
for sign up.
Programming server:

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

Course Staff

Prof. Jelani Nelson (Maxwell Dworkin 125)

TFs: Noah Golowich, Jimmy Jiang

Office Hours:
Tuesday 9/6, 6:00 pm - 8:00 pm, MD 125 with Professor Nelson (future weeks will be Mondays, 5-7pm).
Wednesday, 8:00 pm - 10:00 pm, Quincy dining hall with Jimmy Jiang.
Thursday, 7:00 pm - 9:00 pm, Currier dining hall with Noah Golowich.

Tuesday 5:00 pm - 6:00 pm, location Cruft 309.

In class, 10/11


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.


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 one of C, C++, Java, Python 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 fairly new course (year 3), there are a number of common questions being asked about it.


All assignments will be due at 11:59pm 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 Nelson.   

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)

Also, you will be allowed two late days throughout the semester. You can use at most one late day on any given assignment. You can request a late day via the programming server at

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 (both the text and code) independently and may not check them against each other. There may be no passing of homework papers or program source code 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.

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 or program source codes of students who have taken this course, CS 124, or CS 121 in 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.

Also, for programming problems, you may not use code obtained from an online or other 3rd party source. All code you submit must be code that you yourself write. Furthermore, do not intentionally submit malicious code to the server (e.g. code intended to cause the server to crash, or to steal others' submissions, etc.). You also may not mine data about our private test cases for the specific purpose of discovering their properties beyond what is given in the problem statement. The purpose of programming assignments is, aside from helping you learn, testing your ability to come up with and implement correct and efficient algorithms for various problems. Do not engage in activity that circumvents the spirit of this purpose.

Violation of these rules may be grounds for giving no credit for a homework submission 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 the 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