COMS W3261: Computer Science Theory, Fall 2020


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 will take place on Tuesdays 8:40-9:55am, and on Thursdays 10:10-11:25am (see zoom links on courseworks). Everyone is required to either attend lecture, or go through the recording within the next day (or any combination).

We will use the Piazza discussion board . Use this to ask questions about course material, logistics, and schedule.

Homework and quizzes will be administered through Gradescope (questions about grading should be submitted on gradescope).

Class recordings, lecture notes, homework solutions, and other supplementary files, will be posted on Courseworks.

Office Hours and Teaching staff

The full schedule for office hours can be found here The times listed should be synced to your time zone automatically. This schedule is fairly regular, although may differ slightly from week to week. Be sure to check the calendar when planning to attend office hours. To join, please use this Zoom link at the appropriate time (note that this is different from the zoom link for classes!)

The contact information for the teaching staff is below. You may reach us either by posting a private question on piazza (goes to all staff), or by emailing the instructor and head TA, as appropriate.


Teaching Assistants

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

Below are brief summaries written shortly after each lecture, of what was covered, and readings. Readings refer to the textbook (Sipser), though sometimes may include other pointers or handouts. You are responsible for what was covered in class, which typically follows the textbook. You should make sure to go over each lecture's material before the following lecture (the corresponding textbook chapters are posted). You may, but don't have to (unless otherwise specified) read ahead for next lecture. See Courseworks for lecture recordings and the notes written during the lecture (possibly lightly edited right after).

Practice Sessions

We will have practice sessions, with various TAs and at various times, going over examples and answering questions. These sessions are not required, but can help you learn the material. The TAs will post the relevant materials they went through on courseowrks. Please join using the following zoom link (same as office hours). All times listed are NYC times.


We will have frequent short quizzes that you can take online on Gradescope. The goal of the quiz is to help us get an idea of how the class is doing and where you are having difficulty, and also to motivate you to prepare before each lecture, and to give you an early signal if you are falling behind. Therefore, the quiz grading is designed to emphasize taking the quiz and making an honest effort, rather than answering everything correctly.

For each quiz that you submit, your score will automatically be increased by 25% of the total point value, up to a 100% ceiling. For example, on a quiz with a maximum of 10 points, a score of 2 will be converted to 4.5, a score of 6.5 will be converted to 9, and scores of 7.5 and above will all be converted to 10. A quiz that is not submitted gets a score of 0. The lowest quiz score will be dropped.

You must take the quiz alone, without discussion with anyone else (although you are welcome to go over lecture material with other students). You don't have to finish the quiz in a single pass - you could submit part of it, and then go back and complete the rest (as long as it's before the deadline, and you do it on your own without any discussion with others). You are allowed to use your class notes/ textbook when taking the quiz, although the intention is that the quiz should be solvable without any materials (after you have gone over the previous lectures and digested them). No late quizzes will be accepted.

The quiz is meant to be easier than homework problems, and meant to be completed quickly - within at most 15 minutes if you've already gone over and understood the class material to date. If you find yourself working much longer, contact us and come to office hours (sooner rather than later).


Homework should be submitted via Gradescope. We recommend that you typeset your homework (e.g. using LaTeX), but you may also submit scanned legibly handwritten homework. We will not spend much effort trying to decipher handwriting we find illegible. We will grade answers both for correctness and clarity. We grade what you wrote, not what you meant. If you submit more than one solution to a problem, we will grade whichever solution we want (we may choose the worst one or the one that is easiest to grade).

See below for our policies on lateness, collaboration, etc (quick summary: you have some budget of late hours, you are allowed some limited and clearly acknowledged discussion on homework, you should not cheat, we won't tolerate it).

Class policies

Grading policy

The final grade is determined by quizzes (10%), homework (20%), and four exams (70%) (see more information about quiz grading above). The worst quiz of each student will be dropped, and the worst homework of each student will get half the weight (namely, half of the worst homework will be dropped). Being able to solve the quizzes and homework is crucial for understanding and getting comfortable with the material - it is unlikely you will do well on the exams otherwise. Each of the exams will test one unit of the class, and will be weighted roughly according to how many lectures are covered by this topic (the exact weighting will be announced). There is no cumulative exam (although the material in general builds on earlier material).

There will be 3 exams for the class, and their relative weight is determined by the number of lectures they each cover (9,9,3, respectively). The exams will be given through gradescope, and timed at 75 minutes (you will also get an extra 15 minute grace period to upload your solutions), over a window of at least 24 hours. It is open notes and textbook, but no other resources (in particular, no internet resources are permitted). All work you submit must be your own.
  • Exam 1 window: Thur Oct 15, 3pm -- Fri Oct 16, 3pm. Material: Regular languages (lectures 1-9)
  • Exam 2 window: Thur Dec 3, 6pm -- Fri Dec 4, 6pm. Material: TMs and computability (lectures 14-22).
  • Exam 3 window: Thur Dec 17, 9am -- Fri, Dec 18, 7pm (note: this is the smallest/shortest exam, but the window is extra long to covers the registrar's scheduled final times for both class sections). Material: intro to complexity theory (mid lecture 23-mid lecture 26).

Lateness policy

Late quizzes will not be accepted. For homework, we allow 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 busy with another project, observing a religious holiday, have a minor sickness or another issue.

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

For quizzes and exams, no collaboration is allowed.

For homework, collaboration in groups of two or three students is allowed, but not required (and for most students, I would not encourage it in this class). 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. Obviously, you are also not allowed to look at solutions from other classes, other institutions, previous years, and so on. If you are in doubt, ask the professor. Homework should constitute your own work.

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:

  • COMS W4236: Introduction to Computational Complexity
  • CSOR W4231: Analysis of Algorithms
  • COMS W4261: Introduction to Cryptography
  • COMS W4252: Introduction to Computational Learning Theory.
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:

  • COMS 4115: Programming Languages and Translators.
  • COMS 4705: Natural Language Processing.

Useful and/or Interesting links

  • Tools for drawing finite automata, LaTex, etc:
    • TikZ is a TeX package for programmatically creating graphics which can be used to draw automata. See an example here or here.
    • Finite State Machine Designer is a useful tool to draw automata, which can then be exported to LaTeX (using the TikZ package above).
    • Detexify lets you search for LaTeX symbols by drawing them.
    • Other useful LaTeX packages (included with the standard Texlive distribution) include amsmath, amsthm and amssymb (for typesetting equations), and xyfig (for typesetting automata and trees).
  • Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem", published 1936.
  • If you want to see an explicit specific example of how you might encode a TM as a string, you can check section 2 in this document (written by TA Freddy Kellison-Linn who covered a lecture in 2018).
  • Some short videos suggested by students in the class to help understand proofs by diagonalization:
    • Numberphile short video on countability and on uncountability of the reals (Cantor's proof).
    • video on the undecidability of the halting problem (via a diagonalization proof).
  • Scooping the loop snooper: A proof that the Halting problem is undecidable, in the style of Dr. Seuss, written by linguist Geoffrey Pullum to honor Alan Turing. Copied from his page .
  • Who Can Name the Bigger Number?: An essay by Scott Aaronson, related to uncomputability and Turing Machines (read about the Busy Beaver problem, and more).