COMS W3261: Computer Science Theory, Spring 2015

General information

This is a three-credit required course for the undergraduate CS program. The course prerequisites are Discrete Math (COMS W3203) and, to a lesser degree, Data Structures (COMS W3137), or the instructor's permission.

The course is on Tuesdays and Thursdays. There are two sections:

Lectures for Section 001 will take place from 11:40am-12:55pm in 428 Pupin Laboratories.

Lectures for Section 002 will take place from 10:10am-11:25am in 702 Hamilton Hall.

The final exam for both sections will take place Thursday, May 7th from 10:10am - 12:55pm in 417 IAB.


Instructor and office hours

All TA office hours are in the Computer Science TA room in Mudd. 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.

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

Class Discussion

We will be using Piazza to manage our class discussion board. The class page can be found here.



Recitations will typically be held Fridays from 3:00pm-4:30pm in 312 Math. Handouts with problems covered in recitation are posted on courseworks.


Each homework is due 10 minutes before the start of each class. You must bring a hard copy to class, and also turn in an electronic copy on Courseworks. Homeworks must be typed or legibly written and scanned for the electronic copy. LaTeX is preferred. The electronic submission should be a single pdf file named after your UNI: [UNI].pdf

Grading policy

The homework constitutes 15%, Midterm constitutes 40%, and the final constitutes 45% of the final grade. 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.

Lateness policy

Typically, homework will be due a week from the assigned date. Late homework may be submitted up until 48 hrs after the homework is due for a penalty of 30% off the grade. In some cases the above lateness policy may be canceled, and no late homework will be accepted. You will be notified of this when the homework is given out.

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.


Readings and homeworks will be assigned from Introduction to the Theory of Computation by Michael Sipser, PWS Publishing Company. 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 course are strongly encouraged to pursue some of the advanced courses offered in in theoretical computer science. See the theory group's webpage for more information and a list of past and current theory courses. In particular, the following courses are very closely related in spirit to the topics covered in CS 3261:

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