Computer Science 125: Algorithms & Complexity (Fall 2015)

Madhu Sudan: Computer Science 125: Algorithms & Complexity (Fall 2015)

Syllabus

Course website: http://seas.harvard.edu/~cs125/index.html
Course Piazza site: https://piazza.com/harvard/fall2015/cs125/home or try https://piazza.com/harvard/fall2015/cs125 for sign up.

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

Course Staff

Prof. Michael Mitzenmacher (Maxwell Dworkin 331)
Prof. Madhu Sudan (Maxwell Dworkin 339)

TFs: Sitan Chen, Ramya Rangan

Office Hours:
Wednesday, 8:00 pm – 10:00 pm, Adams dining hall with Sitan Chen.
Thursday, 8:00 pm – 10:00 pm, Eliot dining hall with Ramya Rangan.
Thursday 10/8 onwards, 1:30 pm – 3:00 pm, MD339 with Professor Sudan.

Sections:
Tuesday 5:00 pm – 6:00 pm, location Pierce Hall 100F.

Midterm:
In class, 10/13

Objectives

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

The modern theory of algorithms, focusing on computational efficiency. We will cover algorithms for several specific problems as well as general algorithm design paradigms.
How to reason precisely about computation and prove mathematical theorems about its capabilities and limitations.
Models of computation. We will focus on universal models (such as Turing machines and RAM models) 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).

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 fairly new course (year 2), there are a number of common questions being asked about it.

Why are you introducing this course?

We have long felt that having different entry-points into the CS theory curriculum would be valuable, in recognition of the wide range of mathematical experience that students have. The growth in both CS enrollments and the size of our CS faculty have enabled us to experiment with introducing such alternatives, with CS 20 being one example (for those with less experience) and CS 125 being another (for those with more experience).

We are also excited about re-organizing the introductory material in theoretical computer science, integrating the treatment of algorithms and complexity theory in a way that will should make their relevance to each other more clear.
Does taking CS 125 satisfy the entire theory requirement for the CS concentration (which normally consists of CS 121 and another theory course)?

No. After taking CS 125, you would still need to take another theory course to satisfy the CS degree requirements. This course is meant for students who want to do more theory, not less. Taking CS 125 will put you in a position to take more advanced theory courses (such as those at the 200-level) after one semester rather than two.
Will CS 125 cover everything that’s covered in CS 121 and 124?

No. Our goal is for students to leave CS 125 with the same level of sophistication in reasoning about algorithms and complexity as students who have taken CS 121 and 124, but there will be some specific topics that will not be covered (or will only be touched upon). For example, we will be spending very little time on finite automata, regular expressions, and context-free languages in CS 125. Our expectation is that CS 125 students will be in a position to learn those topics on their own if the need arises in the future.
How high will the workload be?

We’re still figuring this out. We do expect it to be an intensive course, but primarily due to an increase in pace and difficulty, and not due to an increase in the total volume of assignments (as compared to a single semester of CS 121 or CS 124). That is, you may spend more time on the course than you would on CS 121 or 124, but the additional time should be mostly thinking time.
Is the course intentionally offered at the same time as CS 121?

Yes. This is to enable students who are unsure of whether to take CS 125 or 121 to be able to change their mind prior to add/drop date. However, note that the two courses will be covering different material during the first few weeks, so you should keep up with both courses if you might want to switch.
Can I take CS 125 if I have already taken CS 121 or CS 124?

No. Students cannot get credit for both CS 125 and CS 121 or for both CS 125 and CS 124.

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 Sudan.

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:

Weekly problem sets: 50% (lowest score dropped)
Two in-class quizzes (dates TBD): 10% each
Final exam: 25%
Class participation (based on lecture, section, Piazza, office hours, and NB): 5%

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:

Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein. This book is probably worth buying if you are going to study algorithms beyond this course. It is primarily a theoretical text, and it is quite encyclopedic in nature. If you are looking for help with the proofs and mathematics, this is a good book to purchase.
Algorithm Design, by Kleinberg and Tardos. This is also an excellent book, with a different style. It follows portions of the course quite closely, but it is not as encyclopedic as the other book, and in particular assumes a lot more background.
Introduction to the Theory of Computation, by Sipser. This is the textbook for CS 121. It provides an extremely readable and clear coverage of models of computation, computability theory, and computational complexity theory. However, note that we will be covering this material in a different order than in Sipser.
The Nature of Computation, by Mertens and Moore. This text integrates algorithms and complexity material in a very similar way to what we are doing in CS 125. However, it emphasizes breadth over depth, covering a wider variety of topics but with less formality and detail than we will be doing in CS 125.

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

Tentative List of Topics

Sorting (comparison vs. word operations)
Greedy algorithms (e.g. minimum spanning tree)
Divide and conquer (e.g. matrix multiplication)
Dynamic programming (e.g. shortest paths)
Random-Access models of Computation (RAMs)
Turing machines and the (Extended) Church-Turing thesis
Successive approximation algorithms (e.g. Djikstra’s algorithm, network flows)
Using linear programming (e.g. zero-sum games, network flows)
The P vs. NP problem, NP-completeness
Undecidability and its relation to Godel’s Incompletenss Theorem
Randomized algorithms (e.g. hashing, Markov chains) and complexity (RP, BPP)
Potential topics depending on time: approximation algorithms & hardness of approximation, data structures & lower bounds