CS Theory, COMS 3261, Fall 2026

Welcome to CS Theory !

This course is an introduction to the theory of computation, centered around the fundamental question:

What are the capabilities and limits of computation?

For example, which problems can (or cannot) be solved using a computer? Which problems are easy to solve? Is it possible that as technology improves and new brilliant approaches are invented, computers will be able to solve all problems? It turns out, perhaps surprisingly, that the answer to the last question is no. Even before the first computers were built, logicians in the 20th century studied the nature of algorithms and their intrinsic limits; they proved that some problems simply cannot be solved by any algorithm, regardless of what technology or computer we use.

Throughtout the course we will address these questions, starting with how we can even pose them (let alone answer them) rigorously. We will study different models of computation such as automata and Turing Machines. We will examine what makes some problems computationally easy, hard, or impossible to solve on these models, and what this means for our current and future computation capabilities.

The course is highly mathematical and abstract in nature. There will be formal proofs and no programming assignments. Students are expected to be comfortable with discrete mathematics.

Considering how different CS Theory is from other computer science classes you might have taken, you might wonder "Why is this course even mandatory?". It turns out that the topics explored in this course are of fundamental importance across all areas of computer science, from algorithms and machine learning to security and privacy. They also have a deep impact on areas beyond computer science, such as math and philosophy. Finally, the course helps you develop the essential skills of rigorous abstract reasoning and computational thinking.

Now that the course add period is over, we will send announcements through EdStem (which sends email to all students) rather than here. We will also upload the lecture notes from class on Courseworks. The brief lecture summaries and the handouts will still be maintained on this webpage.

Syllabus

Course information This is a 3-credit undergraduate course, required for the CS major. COMS W3203 Discrete Math (or instructor permission) is a prerequisite. This course assumes you are comfortable with reading and writing mathematical proofs. If you have taken COMS 3203 and have had difficulty, come speak to the instructors and teaching staff during office hours, to deal with any issues early on.

Quick Links

The discussion board for this class is hosted on EdStem. For homeworks, quizzes and exams we will use Gradescope. Enrolled students can join both through CourseWorks (see menue on the left)

Lectures notes will be posted on Courseworks. Lectures will generally not recorded with some exceptions.

The textbook for this course is Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. We will generally follow the book in class, but plan some departures. Students are responsible for all material taught in class.

Please read all parts of the page carefully, in particular the class policies. Here is a document compiling tips to succeed in this class.

If you have any administrative questions, you should post a private question to instructors on EdStem (or if it's urgent, also email the instructors with the head TAs CC'ed). Questions with sensitive personal information can be emailed to just the instructors (but read this webpage first, in case it already answers your questions).

Instructors

Tal Malkin
Email: tal at cs dot columbia dot edu William Pires
Email: wp2294 at columbia dot edu

Teaching Assistants

Jonah Stockwell (Head TA) js5384 at columbia dot edu Zak Thayer (Head TA) zjt2106 at columbia dot edu Alice Lin al4576 at columbia dot edu Andrew Wayne Kwok awk2147 at columbia dot edu Charlie Mei jm5912 at columbia dot edu Collins Evans cre2122 at columbia dot edu David Li dl3664 at columbia dot edu Eshan Neil Kabir enk2122 at columbia dot edu Gianna Baker ggb2120 at columbia dot edu Jingxuan (Jeffrey) Lin jl7360 at columbia dot edu Keir Dorchen kd2878 at columbia dot edu Ruby Chang sc5383 at columbia dot edu Tony Fields acf2187 at columbia dot edu Yoav Rafalin yr2477 at columbia dot edu Yuwen Gong jg5014 at columbia dot edu

Class Time and Location
All sections meet Tuesdays and Thursdays.
Section 1: 833 Mudd Building at 8:40am - 9:55am
Section 2: 833 Mudd Building at 10:10am - 11:25am
Section 3: 633 Mudd Building at 11:40am - 12:55pm

Office Hours and Class Calendar

The high level objectives are the ones mentioned above: to understand the fundamental building blocks underlying computer science, while developing computational thinking and abstract reasoning skills. The concrete topics we will cover are the following:

Regular Languages: Before studying general computers, we will look at simpler models of computation called deterministic finite automata and study their properties.
Computability Theory: What problems can and can’t be solve by algorithms ?
Complexity Theory: What problems can and can't be efficiently solved? P vs NP (arguably the biggest open problem in computer science).

Learning Objectives By the end of class, students should be able to…

Write clear mathematical proofs with well explained reasoning (Course long)
Understand the various properties of languages we've seen in class and the relationship between them. (Course long)
Understand the concept of a reduction between languages, including several specific types of reductions, and be able to correctly apply this technique in proofs. (Course long)
Prove that a language is regular in several ways. (1)
Prove that a language is not regular. (1)
Prove that a language is recognizable or unrecognizable. (2)
Prove that a language is dedidable or undecidable. (2)
Analyze the running time of an algorithm and prove that a language is in P or NP. (3)
Prove that a language is NP-complete. (3)

How to succeed in CST

Here is a document compiling tips to succeed in CST.

Grading: Your final grade will be made of the following assessments:

(Checkups 5%) These will be assigned almost every week.
(Homeworks 15%) We plan to have 5 homeworks, each worth 3%.
(Quizzes 60%) 4 Quizzes in class, each worth 15%.
(Final exam 20%) This will be held during the Final Exam period; this will be scheduled by the University Registrar.

The final has two parts:

A required part which will be worth 20% of the course grade.
The required part of the final will be made of the following components:
- Questions that look like the quizzes we had in class: These will cover the last part of the material which no quiz has covered yet.
- Questions which are fairly short and connect all the topics we saw.

For each of the 4 quizzes in class, there will be a corresponding optional reassessment which can be used to improve your score on the corresponding quiz.

The four optional reassessments do not contribute additional points to the 20% final-exam category. They are used only to recalculate the corresponding quiz grades. At the end, your grade for a quiz will be chosen as the maximum of these two:
- (a) Your original grade on the quiz.
- (b) 0.1 × (your original quiz grade) + 0.9 × (your grade on the corresponding final part).
For example, suppose a student earned 60% on Quiz 2 and 80% on the corresponding final-exam reassessment. The recalculated quiz score would be:

0.1(60) + 0.90(80) = 78.

The recorded Quiz 2 grade would therefore be:

max(60, 78) = 78.

If the reassessment produced a score below 60%, the original 60% would remain unchanged.

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

You can write "I do not know" on a problem to receive 15 percent of the points for that problem. This applies to any separate problem on the homework, quizzes, or final. Our reasoning: we think that understanding what you know or don't know is an important objective on its own; it's better to understand exactly what you are supposed to do on a problem but realize that you don't know how to do it, rather than just writing something and hoping it may get you some points. Therefore, we will give partial credit for demonstrating partial mastery, but not for writing facts, definitions, or statements without demonstrating any understanding or relevance.

We will accept regrade requests for assignments on Gradescope up to one week after grades are released. Please read the published solutions and the feedback before submitting a regrade request [Todo: more on how we give feedback]. When we receive a regrade request, if we realize that we made a mistake in applying the rubric, we will correct the mistake. Note that this may result in the grade going down (or up, or no change).

Almost every week we will publish a short checkup set which is made of multiple choice questions. The goal of the checkups 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. After the original due date, there will be additional time where you can retake the checkup as many times as you want (you will see your score after each attempt). We will only keep your last attempt.

The checkup questions are meant to be easier than homework problems, and meant to be completed quickly - within at most 20 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)!

Submissions for the checkups will work with two due dates. You will have a first attempt (you can't see the score of it until we publish grades). Then, we will publish grades, and you will be able to retake the checkup as many times as you want (seeing your grade each time) your final grade will just be your last attempt.

You are expected to take the first attempt seriously and complete it to the best of your ability. In particular, the teaching staff will look at the grades for the first attempts to see which questions the class struggled on. If the class didn't do so well on a question, we will likely go over it in class. Note that you must submit the first attempt to the checkup: if you didn't submit a first attempt you will receive a 0%, even if you complete the second attempt.

The problems on the HW will mostly be proofs. The goal of the HWs is to deepen your understanding and practice using the skills and concepts we’ve seen in class. Each homework is meant to prepare you for the corresponding quiz (or for homework 5, the final), although homework problems may at times be more challenging than quiz ones. Solutions to the HWs will be posted shortly after the due date.

Homework should be submitted via Gradescope. Anonymous homework grading is enabled, so please avoid writing your name or other identifying information on the pages you link to the different problems to be graded on gradescope. If you had discussion collaborators, you must include their names on a separate page of your submission (e.g. the first page), not linked to any problem. PLEASE have each problem start on a different page (it's ok for subproblems to be on the same page). Otherwise the TAs may miss some of your submission, or they might be unable to zoom in enough to read your solutions if you submit one big page with the whole homework. 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.

Note: The responsibility for what is written on a submitted homework belongs soley to the student who submitted it. The teaching staff will try their best to help students and answer their questions. However, our goal is not to tell you what to write on the homework, but rather to help you understand the material, to a point where you understand what exactly the question is asking, and how to tell for yourself whether you had succeeded to solve it. In fact, this is one of the class objectives: for you to be able to tell correct solutions from wrong ones, based on the definitions and formal reasoning. In particular, if a TA (or the professor) tells a student something, even if they accidentally make a mistake in their reasoning, the student is still responsible for whatever they submit and catching any mistakes. We will also not look at your solution in advance to tell you if it is correct or not. Instead, we will try to help you figure out where there is a gap in your understanding, and why you are not confident about your solution (regardless of whether or not it is correct), towards helping you understand the material and do better.

There will be four quizzes each held in class. The goal of the quizzes is to test you've achieved the learning objectives. We will test your knowledge of the material (T/F, short answer, definitions) and ask you to solve new (but similar to already seen) problems and write proofs.

The quizzes will not be cumulative, each will cover a different subset of the material (although some material builds on material from a previous portion of class). The quizzes will be closed book closed notes with no cheat sheets.

The quizzes should take 30 to 40 minutes and will begin at the start of class (make sure to not be late!). After the quiz we will take a short break before resuming class. So as to accomodate for students taking the test with disability services, the lectures following the quizzes will be recorded.

Unless you got permission from the instructors, you must take the quiz during the section for which you are registered.
The tentative dates for the quizzes are as follows:
- October 6th (Tuesday)
- October 22nd (Thursday)
- November 17th (Tuesday)
- December 8th (Tuesday)
Note that these dates might change depending on the speed at which we're able to cover the material. You shouldn't plan on only being able to come to class on the above dates (in fact, you should always attend class!)

See general information about the final above. More specific information will be posted as we get later into the semester.

The final letter grades will be computed on a curve: typically, the cutoff point between B and B+ is somewhere around the average or median, and every standard deviation is a full letter grade above/below. This is only rough, and the exact cutoff points will be selected by us based on the specific distribution. That said, we will respect the following floors:

If your grade is at least 85%: you will at least get an A-
If your grade is at least 70%: you will at least get a B-
If your grade is at least 55%: you will at least get a C-
If your grade is at least 40%: you will at least get a D

Students are expected to adhere to the Academic Honesty policy of the Computer Science Department; this policy can be found in full here. Contact the course staff if you're unsure whether a resource or collaboration is allowed!

AI Policy
The use of generative AI for completing any of the assessments (homework, checkups, quiz) is prohibited. That said, we think it's better if the teaching staff spends their time and efforts on supporting students' learning, rather than enforcing academic honesty and catching cheaters. Thus, we designed the structure of the class in a way that using AI (or someone else's work) on the assignments you get home will mean that you won't do well on the in-person quizzes and final, which are the biggest part of the grade.

While we won't spend lots of resources to try to catch cheaters, if we do catch academic dishonesty we reserve the right to give 0 on the assignment and send you to the Student Conduct office reporting the violation.

Our reasoning: we think that for this class, relying on AI is more likely to be detrimental to your learning. We elaborate on this more in our tips to succeed document, which we encourage you to read, but here's a bit more of our thinking behind the policy above. We think AI can interfere with your learning, even if you try to use it in a way that seems good (not asking it to solve your homework for you, but to explain something). Even if (hypothetically!) you could access an AI which acts as a wonderful tutor that is even better than our teaching staff, it still has many disadvantages. For example, the temptation is too big to ask it questions too early, before being stuck for long enough. Additionally, the line between using AI productively for learning vs using it to save time by shortcutting learning can be hard to determine, and should not be decided by the student who is just learning the material for the first time (even separately from the point that some students rationalize outright asking AI to solve the questions for you). There are other reasons, like the human and social aspects of learning, and benefiting from interaction. But our time is limited, and we don't want to spend it on trying to catch people violating academic honesty -- we rather spend the time supporting students who want to learn, and cultivating a productive environment for that.

Collaboration Policy
For homework, collaboration in groups of up to four students is allowed, but not required. Collaboration in groups of more than four 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 collaborate with other students during office hours, list the office hour you went to (TA name). In any case, you are not allowed to look at written solutions that you haven't written yourself, even if you worked on solving the homework together. Collaboration without acknowledgment is considered cheating.

If you use a source other than material from the course (lecture notes, handout, textbook), explain the material from the source in your own words and acknowledge the source. You are not allowed to rely on sources that solve the same questions we asked, including solutions from other classes, other institutions, previous years, and so on. If you are in doubt, ask the professors (you can make a private post on Edstem).

Late and Missing Work
- Your two lowest checkups will be dropped. This policy is because we understand that you might sometimes forget to submit the checkups in time.
- We will allow some lateness for homeworks 1 to 4. We allow up to 72 hours of lateness with no penalty throughout the semester, provided you use at most 24 hours for any one of homeworks 1 to 4. 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 72 hours total or 24 hours per one assignment will not be accepted.
  
  Note that we won't allow late submissions for HW5, this is to allow us to grade your homeworks in time for the final.
  
  Emergencies
  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 us from having to evaluate and verify your doctor's note or family situation.

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 (but not always) 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 the courseworks page for the class for the notes written during the lecture (possibly lightly edited right after).

Lecture 1: Introduction to class, motivation and overview. Definitions of alphabet, strings, and languages. Tal Malkin Notes | William Pires Notes

Lecture 2: Defined DFA (can be specified with a transition diagram, or with a 5-tuple following the formal definition). Defined the language recognized by a DFA. A language is regular if and only if there exists a DFA that recognizes it. Went through some examples. Reading: Chapter 1.1 (most of it, up to "the regular operations"). Tal Malkin Notes | William Pires Notes

Lecture 3: Review and examples of DFAs and regular languages. We proved (1) Every finite language is regular. (2) The class of regular languages is closed under complement, union, and intersection. The proof for complement and intersection were constructive. Reading: Rest of chapter 1.1 "The regular operations" (except concatenation, we'll get to it later). Tal Malkin Notes | William Pires Notes

Lecture 4: Introduced the Myhill-Nerode (MN) theorem. Explained what it means for two strings to be distinguishable or indistinguishable with respect to a language L. A language is regular if and only if ~_L has finitely many equivalence classes. The number of equivalence classes of ~L (if finite) is equal to the smallest number of states in a DFA for L. We used MN to prove that L={a^nb^n | n \geq 0} isn’t regular. Reading: See our typed lecture notes (covering this lecture and the beginning of the next one). We wrote the notes and also recorded this class, since the material is not in the textbook. Also see the lecture notes written during class here: Tal Malkin Notes | William Pires Notes
Lecture 5: We reviewed the Myhill-Nerode theorem and saw some more examples. Started discussing Non-Deterministic Finite Automata (NFA), informally. Intuition on how to interpret NFA computation on a string (via computation tree that captures all possible computations, or via "I'm feeling lucky" guessing). Reading: Chapter 1.2 up to "equivalence of NFAs and DFAs". Tal Malkin Notes | William Pires Notes

Lecture 6: Formal definition of NFAs. Did some more examples, we revisited the challenge question from the end of lecture 2, which is much easier to solve with an NFA than directly construct a DFA. Proved that a language is regular if and only if it is recognized by an NFA (one direction of the proof is easy, while the other direction involves the subset construction, converting any NFA to an equivalent DFA). Reading: Chapter 1.2 "Equivalence of NFAs and DFAs".
Lecture 7: Defined more operations on languages (ie sets): concatenation, power, Kleene star. Proved regualar languages are closed under these operations (using NFAs). Reading: The definitions of the operations are at the very end of 1.1, closure is at the last part of 1.2.

Lecture 8:Went over regular expressions and the languages they generated. We did some example. We proved that a language is generated by a regular expression if and only if it is regular. One direction (every regular expression has an equivalent NFA) followed from the closure properties we previously proved. For the other direction: any NFA can be transformed to an equivalent regular expression, we skipped it (but you can read about it in the book if you want). Reading:Chapter 1.3 up to lemma 1.60.

Lecture 9: Quiz 1, wrapped up regular languages and talked about what's coming soon.

Lecture 10: Introduced the formal definition of TMs, computation of a TM on a given input (it can accept, reject, or run forever), and the language recognized by a TM. Defined a decider (a TM that halts on every input), recognizable languages and decidable languages. Reading: Chapter 3.1 Readings for next time: The rest of chapter 3

Lecture 11: Defined input-output TM and a computable function, and a couple examples of computable functions that can be used as "subroutines" in the construction of other TMs. Discussed several variants of TM models, and started to show their equivalence to the standard model. These include: a TM with a "stay put" option, a TM with a doubly infinite tape, and a TM with a fixed number of multiple tapes. Readings for today and next time: Chapter 3.2

Resources

Handout and review material:

To check and refresh on your discrete math prerequisite for the class, read Chapter 0 of Sipser's textbook. Our first checkup will also test some discrete math background. You can also check Tim Randolph's HW0 (here are the solutions).

If you have difficulty with any of the above, then if you have not yet completed 3203 discrete math, you should drop this class and take 3203 first; otherwise, come speak to the instructors and teaching staff during office hours, to deal with any issues early on.

Below are handouts generated by the teaching staff as a supplement to class material. These do not constitute required material for the class, but rather meant to support your learning and understanding. Most of the resources below provide further examples and review of what was already covered in class, but some of the resources provide new (and completely optional) more advanced material for interested students -- these will be clearly marked.

Challenge Problems

- Excellent videos by Sipser (the author of textbook)
- LaTeX Template for Assignments
- 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).
- Webpage for previous versions of the course. You can find lecture notes, handouts, previous HWs there if you want some extra material it can be great. However we might do things differently, so make sure it's relevant for the course.
- Llamautomata: A game to help build comfort with designing automata that recognize different languages.

Some of Columbia's resources to support you:

If you have special needs because of learning, physical or other disabilities, it is your responsibility to contact Disability Services . They will then contact us regarding your accomodations. Note that if you're a Barnard student, you should contact CARDS instead.
Counseling and Psychological Services.