COMS W3261: Computer Science Theory, Spring 2018


General information

This is a three-credit required course for the undergraduate CS program. The course requires Discrete Math (COMS W3203) as a prerequisite, or the instructor's permission.

Lectures for Section 001 will take place MW 10:10am-11:25am in 207 Math

Lectures for Section 002 will take place MW 8:40am-9:55pm in 207 Math.


The two sections of this class will have a combined Piazza, which is available here. Use this to ask questions about course material, logistics, and schedule. Questions about grading should be emailed directly to the TA who graded the problem in question.

Instructor and office hours

All TA office hours are in the Computer Science TA room in Mudd unless otherwise noted.

All of Professor Malkin's office hours are in 514 CSB. If you do not have swipe access to the computer science building, please ask someone in the office to let you in.


Teaching Assistants

Office hours by day

Class description and syllabus

This course is an introduction to models of computation, computability, and complexity. We will ask questions like: How do we define the abstract notion of "computation" or a "computer"? What problems can be computed? What problems can be computed efficiently? Can we prove that some problems can never be computed, no matter how fast our computers become? The course is highly mathematical and abstract; in particular, there will be minimal programming assignments (if any) and homework problems will frequently involve proving or disproving various assertions. Students are expected to be comfortable with the material covered in Discrete Math (W3203) or the equivalent.

Topics (not exhaustive): automata and the languages they define, context-free grammars and the languages they define, Turing machines, basic complexity theory (such as P vs. NP).

Lecture Summaries

Practice Sessions


Each homework is due electronically through Courseworks. Homeworks must be typed or legibly written and scanned. LaTeX is preferred but not required. The electronic submission should be a single pdf file named after your UNI: [UNI].pdf. See policies for lateness etc.

Class policies

Grading policy

The final grade is determined by homework (15%), in-class midterm (40%), and in-class final evalution (45%). The worst homework of each student will be dropped. Doing the homework is crucial for understanding and getting comfortable with the material; it is unlikely you will be able to do well on the tests without doing the homework. You are advised to start the homework early.

There will also be extra credit problems on some of the homeworks and possibly on the tests as well. Those problems are meant as learning opportunities for students who would like more challenge, but are not very consequential for your final grade. Specifically, the weighted average and curved cutoffs for letter grades will be determined ignoring the extra credit scores. Then, for people very close to the borderline/cutoff between two letter grades, the extra credit could help push them over the line. For other people, it will make no difference.

The in-class midterm evaluation will take place during class on Monday 2/26.

The in-class final evaluation will take place during the last class, Monday 4/30.

Lateness policy

Typically, homework will be due about week from the assigned date, submitted elecronically through Courseworks. You are allowed up to 120 hours of lateness with no penalty throughout the semester, provided you use at most 48 hours for any one homework. Any part of an hour (e.g., a minute) counts as a full hour. This lateness time is provided to allow for last minute upload/internet problems, or in case you're sick, going out of town, busy with another project, observing a religious holiday, or any other reason that may come up. Note that this is in addition to dropping the worst homework, so you have lots of flexibility for emergencies or planned delays that come up.

Any homework that is late beyond the 120 hours total or 48 hours per one assignment will not be accepted.

In some cases the above lateness policy may be canceled, and no late homework will be accepted for a certain homework (e.g., before a test). You will be notified of any such case when the homework is given out.

For other emergenices (e.g., if you have to miss an in-class exam because of a serious family or medical emergency), please provide all necessary documentation to your advising dean, and have the dean contact me to discuss appropriate accommodations. This maintains your privacy, and saves me from having to evaluate and verify your doctor's note or family situation.

Collaboration policy

All students are assumed to be aware of the computer science department academic honesty policy . Homework should constitute your own work. Collaboration in groups of two or three students is allowed, but not required. Collaboration in groups of more than three students is not allowed. If you do collaborate, you must write your own solution (without looking at anybody else's solutions), and list the names of anyone with whom you have discussed the problems. If you use a source other than the textbook in doing your assignment, explain the material from the source in your own words and acknowledge the source. In any case, you are not allowed to look at written solutions of any other student, even if you worked on solving the homework together. Collaboration without acknowledgment is considered cheating.

Every student caught cheating will be referred to Colubmia's office of Student Conduct and Community Standards, as well as subject to academic penalty in the class.


Readings and homeworks will be assigned from Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. Copies are currently available at the Columbia bookstore. The book's website and errata are available here. We will generally follow the book in class, but some departures are possible. Students are responsible for all material taught in class.

Optional text: Introduction to Automata Theory, Languages and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman

CS 3261 constitutes the last CS Theory course required to be taken by all CS majors. Students interested in the material covered by this coure are strongly encouraged to pursue some of the advanced courses offered in theoretical computer science. In particular, the following courses are very closely related in spirit to the topics covered in CS 3261:

There are often also 4995 and 6998 classes related to theoretical CS.

In addition, the following courses (and quite a few others!) benefit from and relate to some of the topics covered by our course:

Useful links