Computer Science Theory: Fall 2024

Teaching staff and Office Hours

Teaching staff:

Professor: Tal Malkin
Head TAs: William Pires (wp2294)
TAs: Angel Cui (lc3542), Anum Ahmad (aqa2001), Hellen Zhao (hz2843), Kiru Arjunan (ka2893), Owen Keith(ock2103), Owen Kichizo Terry (okt2002), Yihan Shen (ys3524), Yizhi Huang (yh3667), Zachary Jacob Thayer (zjt2106), Ziheng Huang (zh2556)

If you have any administrative questions, you should post a private question to instructors on Edstem, or email the professor with the head TA CC'ed. Questions with sensitive personal information can be emailed to just the Professor (but read this webpage, including class policies below, in case it already has the answer to your question).

Office hours: The full schedule can be found in the course calendar:

Note the different locations for different office hours! In-person office hour locations include: CS TA room on 1st floor Mudd, CSB 5th floor lounge, Milstein 502 in Barnard, and 514 CSB for Prof. Malkin. There is one TA who will be holding office hours over zoom, and occasionally other TAs or the professor may also do that. Make sure to check the calendar (including location/modality) before showing up for office hours.

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 (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 (9/3): Introduction to class, motivation and overview. Definitions of alphabet, strings, and languages. Examples.
Readings: Chapter 0 (we didn't go over most of it in class, but this is background material you're supposed to know from discrete math). See more discrete math background below).
Lecture 2 (9/5): 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).
Lecture 3 (9/10): Review and examples of DFAs and regular languages. Every finite language is regular. Proved that the class of regular languages is closed under complement, union, and intersection (and the proofs were constructive, showing how to construct the appropriate DFA from the given DFAs of the underlying languages).
Reading: End of 1.1 (except the concatenation, we will get back to it). See also handout 2.
Lecture 4 (9/12): Proved that every regular langauge satisfies the pumping lemma, intuitively saying that every string in the language that is long enough (above some pumping constant for the language) must have a non-empty portion that can be pumped down or up any number of times and still be in the langauge. Thus, to prove that a language is not regular, it suffices to show that it does not satisfy the pumping lemma. Discussed how to do this, and showed some examples. Also discussed how to show non-regularity by using closure properties.
Reading: Chapter 1.4
Lecture 5 (9/17): Review of pumping lemma and more examples. The Myhill-Nerode theorem, which characterizes regular langauges and the minimal DFAs for them, and also gives another way to prove non-regularity. We stated the theorem and showed a brief example. This is not a required part of the class material (but can be useful). Started discussing Non-Deterministic Finite Automata (NFA), informally. Intuition on how to interpret NFA coputation on a string (via tokens or computation tree that capture all possible computations, or via "I'm feeling lucky" guessing).
Reading: Chapter 1.4 for pumping lemma, handout 3 for the Myhill-Nerode theorem, and handout 4 for review and more examples. Beginning of Chapter 1.2.
Lecture 6 (9/19): Defined NFAs formally, and saw some examples. As an aside, one of the examples demonstrated that an NFA for a language may be exponentially smaller than the minimal DFA for the langauge. The other example 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). Gave an example.
Reading: 1.2 (first two parts).
Lecture 7 (9/24): Defined more operations on languages (ie sets): concatenation, power, Kleene star. Proved regualar languages are closed under these operations (using NFAs). Also noted an alternative proof for closure under union using NFAs. In one section defined regular expressions and the languages described by them.
Reading: the definitions of the operations are at the very end of 1.1, closure is at the last part of 1.2, and regular expressions are the first half of 1.3 (the latter is the assigned reading).
Assigned Reading: before next lecture read Sipser's 1.3 first half, pages 63-66, also available here (just to get used to regular expressions and see examples, so that you can follow the proof in class on Tuesday).
Lecture 8 (10/1), by William Pires: 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 we showed that any NFA can be transformed to an equivalent regular expression by going through a GNFA.
Reading: 1.3
Lecture 9 (10/3): Wrapped up discussion of regular languages with some comments and applications. Overview of where we are in class and what is coming, including brief mention of some other classes of languages / models of computation. We then gave a high level overview of context free languages, mentioning all the following (without any proofs). We defined context-free grammars and the langauges they generate, stated that every regular language is context free, gave examples of non-regular langauges that are context free. Stated that a language is context free (generated by CFG) if and only if it can be recognized by a push-down automaton (PDA), which is like an NFA equipped with a stack. Mentioned that there is a "tandeom pumping lemma for CFL" that can be used to prove a language is not context free (but we did not even state the lemma), and gave some examples of languages that are not context free. Mentioned that the class of CFL is closed under the regular operations, but not closed under complement and interesction. CFL are very useful in CS (compilers, NLP, and more), as well as related to (and originating from) study if natural languages in lingusitics.
Reading: The book has a lot on CFL (chapter 2), which you are encouraged to read if interested, but it's not required for class - you are only responsible for the high-level overview given in class.
Lecture 10 (10/8): Introduced Turing Machines: some motivation, definition, examples, and contrast with DFAs.
Reading: 3.1
Lecture 11 (10/10): Reviewed and completed 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. Mentioned that in the hierarchy of language classes we've defined so far -- regular, context free, TM-recongizable, TM-decidable, all languages -- each is a proper subset of the next (as we will prove later). Showed one full example TM. Defined input-output TM and a computable function, and a couple examples of computable functions that can be used as "subroutines" in the contstruction of other TMs.
Reading: 3.1, definition 5.17 (computable function)
Coming up: the rest of chapter 3
10/15: in-class midterm covering lectures 1-9.
Lecture 12 (10/17): Gave a few more examples of computable functions that can be used as subroutines. Discussed several variants of TM models, and showed 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.
Reading: beginning of 3.2. Also note that the lecture notes for this lecture included a pretty detailed example (added after class) of one step in the simulation of a multi-tape TM with a standard TM.
Lecture 13 (10/22): Defined non-deterministic TM (NTM) and proved its equivalence to a standard TM. The proof involved a simulation of the NTM with a deterministic one by doing a breadth-first search of the computation tree. We gave some informal comments (without any formal definitions or proofs) on the complexity of the transformations we have seen: we mentioned that the transformation from multi-tape TM to a standard one incurs a quadratic overhead in running time, and that this overhead is known to be inherent; our transformation from NTM to a standard one incurs an exponential overhead in running time -- whether or not this is inherent is the biggest open problem in computer science (it's essentially the P vs NP problem which we will cover later). We listed quite a few other models that are known to be equivalent to TMs, and stated the Church-Turing thesis. We will identify algorithms with TMs, and use high level descriptions. Reviewed what needs to be proved to prove a language is recognizable and to prove that it is decidable. Proved that the class of decidable languages is closed under complement, and noted why this proof does not work for the class of recognizable languages (that class is in fact not closed under complement, as we will see).
Reading: most of 3.2, 3.3.
Lecture 14 (10/24): Proved that a language L is decidable if and only if both L and its complement are decidable. Along the way, introduced the idea of running two machines in parallel, for ever-increasing number of steps. Introduced the important idea that every algorithm/TM can be encoded as a string (or an integer), and thus fed as an input to another algorithm (which may manipulate it, run it, try to reason about it, etc). Similarly, other objects (DFAs, graphs, etc) can also be encoded as strings. Showed several examples of decidable languages, including: every regular language, the languages A_DFA, A_NFA, E_DFA and started EQ_DFA (completed in the following lecture).
Reading: 4.1 (first part), Theorem 4.22. Not required for class, but if you want to see an explicit specific example of how you might encode a TM as a binary string, you can check section 2 in this document (written by TA Freddy Kellison-Linn who covered a lecture in 2018). We will not care about the specific alphabet or encoding, just that there's one that can be fixed and algorithmically checked.
Lecture 15 (10/29): Went through a common mistake on Quiz 6. Completed the proof that EQ_DFA is decidable. Mentioned (without proof) that A_CFG, E_CFG are decidable, but EQ_CFG and the ambiguity problem for CFG are not. Proved that A_TM, the acceptance problem for TMs, is recognizable. Specifically, it is recognized by the universal TM (which encompasses "general purpose computation"), which takes as input a description of an arbitrary TM M and a string w, and simulates M on w. Discussed why this universal TM is not a decider, and mentioned that _TM is in fact undecidable (as we will prove). Started showing that NE_TM is recognizable.
Reading: 4.1
Lecture 16 (10/31): Showed that NE_TM is recognizable, using the "dovetailing" technique. Outlined and motivated the plan for the rest of the section on computability, towards proving that some languages are not decidable, or not recognizable. Defined when sets have the same cardinality, and when a set is countable. A subset of a countable set is a countable set. Examples of countable sets, including: the set of all strings over any (finite) alphabet, any language (set of strings), the set of all TMs, the set of TM-recognizable languages, the set of TM-decidable languages. Proved that the set of all languages (over any alphabet with at least two symbols) is not countable. The proof uses Cantor's diagonalization argument (that he originally used to prove that the set of reals is not countable). Concluded that there exists a language that is not recognizable (in fact, there are uncountably many languages that are not recognizable, while only countably many are).
Reading: 4.2
Lecture 17 (11/07): A set is countable if and only if every element has a finite description (ie, can be written as a finite string). Mentioned informally that a language is recognizable if and only if there is an enumerator algorithm for it (hence the name "recursively enumerable"). In other words: while every language L is countable (there exists a bijection f from the naturals to L), a language L is recognizable if and only if there's an actual algorithm that can compute and output the values of this bijection f(1), f(2), f(3),... (namely all elements of L). Proved that A_TM is not decidable -- the proof used a diagonalization technique (or "the barber paradox"). Proved that the halting problem Halt_TM is not decidable (by reducing from A_TM).
Reading: 4.2. You may also like this this poem-proof for undecidability of the halting problem (via diagonalization). (Note: we used diagonalization to prove A_TM is not decidable, and then showed that if the halting problem HALT_TM was decidable, A_TM would also be. The above directly proves the halting problem is not decidable via diagonalization - this proof is very similar to our poof for A_TM.)
Lecture 18 (11/12): Defined Turing reductions. If A is Turing-reducible to B and B is decidable, then A is decidable. Equivalently, if A is Turing-reducible to B and A is undecidable, then B is undecidable. Noted that last time we actually proved that A_TM is Turing reducible to Halt_TM. Proved that the emptiness problem E_TM is undecidable, by reduction from A_TM. Proved that the equivalence problem EQ_TM is undecidable, by reduction from E_TM. Stated and discussed significance of Rice's theorem, then showed an example of how to apply it: proving that REG_TM is not decidable. Said a couple of words about the proof. The full proof (and more) was added after class to the lecture notes (on courseworks), but it is not a required part of class material.
Reading: 4.2, 5.1 (beginning), 6.3 (note: Sipser's "informal notion of reducibility" in chapter 5 is the same as the formal notion of Turing reducibility which he defines in section 6.3), problem 5.28 and its solution.

Quizzes

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

You will always have at least 24 hours for each quiz.

Quiz 1 out 9/5, due ~~Sun 9/8~~ Mon 9/9, 11:59pm.
Quiz 2 out 9/20, due Mon 9/23, 11:59pm.
Quiz 3 out 9/28, due Mon 9/30, 11:59pm.
Quiz 4 out 10/19, due Mon 10/21, 11:59pm.
Quiz 5 out 10/27, due Mon 10/28, 11:59pm.
Quiz 6 out 11/10, due Mon 11/11, 11:59pm.

Homework

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, include their name on a separate page of your submission, 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.

See below for our policies on lateness, collaboration, regrade requests 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).

You will always have at least a week for each full homework (there will also likely be up to two half-sized homeworks before exams).

Homework 1 out 9/15, due Sun 09/22, 11:59pm.
Assigned reading before October 1st class: read Sipser's 1.3 first half, pages 63-66, also available here (just to get used to regular expressions and see examples, so that you can follow the proof in class on Tuesday).
Homework 2 out 10/5, due Sat 10/12, 11:59pm. Can only use late hours up to Sun 5pm.
Homework 3 out 10/26, due Fri 11/8, 11:59pm (after extension).

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) tell a student something, even if they accidentally make a mistake in their reasoning, the student is still responsible for catching that (at least if they are going to write something based on it), by fully understanding the problem and solution. 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.

Class policies

To receive disability-related academic accommodations for this course, students must first be registered with their school's Disability Services (DS) office. Detailed information is available online for both the Columbia and Barnard registration processes. Refer to the appropriate website for information regarding deadlines, disability documentation requirements, and drop-in hours(Columbia)/intake session (Barnard). For this course, students registered with the Columbia DS should refer to the DS Testing Accommodations page for more information about accessing exam accommodations.

Grading policy

The final grade is determined by quizzes (10%), homework (20%), and two exams (70%) 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.

There will be two exams, in class:

Exam 1: in class, Tue October 15th.
Exam 2: in class, Tue December 5th (last class).

There is no cumulative exam (although the material in general builds on earlier material).

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). If you write "I do not know how to solve this" on a homework or exam problem, you will get 15% of the points for that problem.

We will accept regrade requests for assignments on Gradescope up to one week after grades are released. Please read the published solutions and the rubric before submitting a regrade request. To submit a regrade request on Gradescope, click on the question and click "Request Regrade", then write a few sentences explaining why you think your answer is correct. 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).

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

Textbook

Readings and homeworks will be assigned from Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. 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

Do I have the Prerequisites for the Class?

To check and refresh on your discrete math prerequisite for the class, read Chapter 0 of Sipser's textbook (here is a pdf of this chapter if you don't have the book yet). Quiz 1 will also test some discrete math background. You can also check Tim Randolph's HW0 (here are the solutions). Finally, check out handout 1 below, with a discrete math review sheet.
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 professor and teaching staff during office hours, to deal with any issues early on.

Handouts and Review Resources

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.

Handout 1: Discrete Math Review Sheet by Anum Ahmad and William Pires.
Lecture Recordings from Michael Sipser's course. This is a great ressource if you're looking for more explanations on the material seen in class.
Handout 2A: DFA review and practice problems and Handout 2B: DFA practice with solutions by Angel Cui and Owen Keith.
Handout 3: Myhill-Neorode Theorem. This is an optional handout, not required as part of class material. It presents the beautiful and fundamental Myhill-Nerode theorem, which characterizes regular langauges, and can be used to prove a language is not regular.
Handout 4A: Proving Non-Regularity: Review and Practice Problems and Handout 4B: Solutions by Hans Shen and Hellen Zhao.
Handout 5: Example from Class (Subset Cosntruction and more).
Handout 6A: NFAs and Regular Expressions: Practice Problems and Handout 6B: Solutions by Kiru Arjunan and Ziheng Huang.
Midterm review session by Yizhi Huang and Owen Terry, CSB 451, Sunday October 13th at 6-7:30pm and 8-9:30pm.
- Handout 7A: Midterm Review Questions
- Handout 7B: Midterm Review Solutions
A great tool to draw TMs and also run them.
Handout 8A: Turing Machines and Decidability: Review and Practice Problems and Handout 8B: Turing Machines and Decidability with solutions by Anum Ahmad and Zachary Thayer.
Some resources that may be interesting or useful, but are not part of the class required material:
- This is a handout written for a previous iteration of the class by TA Freddy Kellison-Linn. Section 2 includes a specific examples of how you might encode a TM as a binary string. This is not required for class, but may be helpful for you to be convinced that it is indeed reasonable to assume that we can fix an encoding which can be algorithmically checked for validity.
- Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem", published 1936. (possibly more readable font for the symbols here).
- 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 .
- Some short videos suggested by students to help understand proofs by diagonalization (disclaimer: I did not watch these!)
  - 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).
- 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).
Handout 9A: Countability, Turing Reductions, Proving undecidability: Review and Practice Problems and Handout 9B: Solutions by Owen Keith and Owen Terry
A blog post by Scott Aaronson that discusses (informally) how to prove Gödel's incompleteness theorem and a variation of it due to Rosser, using the undecidability techniques we have seen in class. This is not required class material!

COMS W3261: Computer Science Theory, Fall 2024

Recent Announcements

General information