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
The course is on Tuesdays and Thursdays. There are two sections:
Lectures for Section 001 will take place from 10:10am-11:25am in 207 Mathematics.
Lectures for Section 002 will take place from 11:40am-12:55pm in 428 Pupin.
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.
- Prof. Tal Malkin
- Email: tal at cs dot columbia dot edu
- Luke Kowalczyk (Head TA)
- Email: luke at cs dot columbia dot edu
- Rudra Gopinath
- Email: rg2986 at columbia dot edu
- Hidy Han
- Email: yh2635 at columbia dot edu
- Frederick Kellison-Linn
- Email: fjk2119 at columbia dot edu
- Ethan Liu
- Email: yl3156 at columbia dot edu
- Jiahui Liu
- Email: jl4161 at columbia dot edu
- Flora Park
- Email: flora dot park at columbia dot edu
- David Rincon-Cruz
- Email: dr2884 at columbia dot edu
- Steven Shao
- Email: y dot shao at columbia dot edu
- Anand Sundaram
- Email: as5209 at columbia dot edu
- Michael Tong
- Email: mct2159 at columbia dot edu
- Cindy Wang
- Email: xw2368 at columbia dot edu
Office hours by day
- Saturday (5/6)
- David Rincon-Cruz - 12:00pm-2:00pm
- Jiahui Liu - 2:00pm-4:00pm
- Cindy Wang - 4:00pm-6:00pm
- Sunday (5/7)
- Jiahui Liu - 10:30am-12:30pm
- Michael Tong - 2:00pm-4:00pm
- Luke Kowalczyk - 4:00pm-6:00pm
- Monday (5/8)
- Anand Sundaram - 10:00am-12:00pm
- Flora Park - 12:00pm-2:00pm
- Steven Shao - 4:30pm-6:30pm
- Tuesday (5/9)
- Final - 9:30-11:30am - location TBD
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
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).
We will be using Piazza to manage our class discussion board. The class page can be found here.
Lecture 1 (1/17) Motivation and overview of the
class. Definitions of alphabet, strings, and
languages. Examples and definition of DFA and the
language recognized by a DFA.
Readings: Chapter 0 (also includes some background
from discrete math), Chapter 1.1 (first subsection).
- Lecture 2 (1/19) DFAs and the languages
recognized by them, regular languages. All finite
languages are regular. Examples of infinite regular
languages and intuition for languages that may not be
regular. HW0 out (not for submission).
- Lecture 3 (1/24) Definition and Examples of
NFAs, how it computes (via tokens or a computation
tree), and the language recognized by an NFA. Every NFA
has an equivalent DFA (subset construction), and thus a
language is regular if and only if it is recognized by
an NFA. Readings: 1.2. See also pages 7-9 in the HW0 Solutions, which includes
the example we saw at the end of class. HW0 (not) due.
- Lecture 4 (1/26) Completed the formal
specification of the subset construction, and discussed
intuition. We proved that for the language of binary
strings with n-th to last bit being 1, there's a n+1
state NFA, but any DFA recognizing this language must
have at least 2^n states. We concluded that any generic
compiler from NFA to DFA must have an exponential
blow-up in the number of states since for some languages
(though not all) the best DFA is exponentially larger
than the best NFA. We then defined operations on
languages (complement, union, intersection,
concatenation, power, Kleene star) and said that the
class of regular languages is closed under all these
operations, although we only proved closure under
complement so far.
Reading: 1.1,1.2, as well as
the following handout.
- Lecture 5 (1/31) We gave two different proofs
that the class of regular languages is closed under the
union operation (building an NFA and a DFA), and two
proofs that it is closed under intersection (building a
DFA, and using De Morgan law). We also proved that the
class of regular languages is closed under concatenation
and under the star operation (by building an NFA).
Defined the regular operations (union, concatenation,
star) and gave an overview of what we will see next time
(regular expression and their equivalence to DFA and
Reading: 1.1 starting with Theorem 1.25, 1.2. Optional
(not covered in class):
Notes on the Myhill-Nerode
Theorem. HW1 due, HW2 out.
- Lecture 6 (2/2) Defined regular expressions,
proved that a language is generated by a regular
expression if and only if it is regular (getting a NFA
from regular expression was mostly proved last time, the
other direction involved a transformation from NFA to
regular expressions, using GNFAs and ripping states).
Noted that the transformation from regular expression to
NFA results in an NFA with a number of states linear in
the length of the RE (this can be proved based on our
constructions, though we did not go through the
proof). However the ransformation from NFA to
RE can give a RE of exponential length compared to NFA
size (noted without proof).
Examples and discussion.
- Lecture 7 (2/7) Proved that every regular
language satisfies the pumping lemma, and showed how
to use it to prove a language is not regular (proving
that a language L does not satisfy the pumping lemma
implies that L is not regular). We saw several
examples. Noted that the pumping lemma is not a
characterization (some non-regular language also satisfy
it) so it doesn't always work to prove a language not
regular (but it works often enough to be very useful).
Reading: 1.4. HW2 due, HW3 out
- 2/9: Snow day, class was canceled.
Please read the following short
handout, wrapping up our
topic of how to prove a language is not regular.
- Lecture 8 (2/14) Wrapped up discussion on
regular languages, their applications, and how to prove
a language is not regular. Defined context-free
grammars and the languages they generate, with examples.
Defined parse trees, leftmost derivations, and rightmost
derivations (each derivation corresponds to a parse
tree; a parse tree can have many corresponding
derivations, but only one leftmost derivation and only
one rightmost derivation). Defined ambiguous grammars
and gave examples. Defined inherently ambiguous
languages and gave an example (without proof).
Reading: 2.1. HW3 due.
- Lecture 9 (2/16) More examples of context free
grammars, including an example with a detailed proof of
correctness (proving that it generates a given language),
and a proof that the language of valid regular expressions
is context free but not regular. Defined Chomsky Normal
Form (CNF), and stated (without proof) that every CFG has
an equivalent one in CNF. Defined a right-linear (or
regular) grammar (a CFG where each rule is of the form A
→ aB or A → a or A → ε. Stated
that a language is regular if and only if it can be
generated by a right-linear grammar (we didn't prove this
but sketched the main idea). This also
implies that every regular language is context free (we
will see other proofs of that). Proved that the class of
context free languages is closed under the regular
operations (union, concatenation, star). This can also be
used to prove that every regular language is context
free. Mentioned that the class of context free languages
is not closed under intersection or complement
(we will prove later). Reading: 2.1. (part of HW4
- Lecture 10 (2/21) Pushdown Automata (PDA):
definition and examples. Brief informal discussion of
deterministic PDAs. A language is context free if and
only if it can be recognized by a PDA (we showed how to
transform a CFG to a PDA, but skipped the other
direction). As a corollary, every regular language is
context free (since the transformation from an NFA to a
PDA is trivial). Reading: 2.2. (second part of HW4
- Lecture 11 (2/23) We stated and proved the
tandem pumping lemma for context free languages, and
showed how to use it to prove that a language is not
context free (this will not be on the midterm).
We noted that a finite state machine with two
stacks (rather than just one that a PDA has) could
recognize both non-context free languages we saw as
examples (we will see later that a finite state machine
with two stacks is at least as powerful as your favorite
We proved that the class of context free languages is
not closed under intersection, nor under
complement. Wrapped up the topic of context free
- Lecture 12 (2/28)
Introduction to computability and Turing Machines (TM) and
overview of upcoming topics.
TM definitions: machine, configurations, a language
recognized by a TM. Examples.
Reading: 3.1. HW4 due.
- Midterm (in class)
- Lecture 13 (3/7)
Review of TM, definition of a decider (capturing "an
algorithm"), definition of a recongizable language and a
decidable language. Detailed complete example (with state
diagram) of a TM recognizing unary strings of lenght a
power of 2 (which is not a CFL). Definition of an
input-output TM and of a computable function. Several
examples (in various level of detail) of "subroutines"
that could be implemented with an input-output TM.
Mentioned some equivalent variants of TM: a TM that can
move right, left, or stay put, and a TM that has a doubly
infinite tape (we briefly outlined how the equivalence can
be proven in both these cases).
Reading: 3.1, 3.3 (and definition 5.17).
- Lecture 14 (3/9)
Defined a multi-tape TM, and proved equivalence to a
standard TM. Noted that this transformation from multi-tape to
single-tape TM incurs a qudartic overhead in running time,
and that this overhead is known to be inherent (we didn't
prove this). We then defined non-deterministic TMs, and
proved its equivalence to standard TMs. The
transformation from a NTM to a TM involved performing a
breadth-first search of the computation tree, and incurs
an exponential overhead in running time. Noted that
whether or not this is inherent (namely whether there is a
more efficient simulation of NTM by a deterministic TM) is
related to the P vs NP problem, the biggest open problem
in computer science, which we will cover later in the
Midterms returned. HW5 out.
- Lecture 15 (3/21)
Overview of equivalent models to TM (including many that we
haven't proved). Church-Turing thesis and
discussion. Shifting to a high-level algorithm/TM
description. Brief discussion of encodings of objects as
strings. Showed that the following languages (decision
problems) are decidable: Acceptance (membership) problem
for DFA, NFA, Emptiness problem for DFA, Equivalence
problem for DFA (didn't prove) and Acceptance problem for
CFG (in the second section we didn't get to the last two
examples until the following lecture).
Reading: 3.3, 4.1
- Lecture 16 (3/23) Showed that any context free
language is decidable (using the fact that acceptance
problem for CFG is decidable). Mentioned (without proof) that the
emptiness problem for CFG is also decidable, but
equivalence problem for CFG is not decidable, and checking
ambiguity of a CFG is not decidable (we will see methods
to prove undecidablity soon). Discussed the
Acceptance problem for TMs (the language A_TM), and showed
that it is recognizable, by the universal TM (that takes
as input a description of a TM M and a string w, and runs
M on w). Discussed the importance of this idea that
an algorithm can be expressed by a string and can be fed as
input to another algorithm, which can then manipulate it,
simulate it, try to reason about it, etc.
Discussed why the universal TM is not a decider for A_TM and
some intuition for why deciding A_TM may be hard (we will
prove it's undecidable soon).
Showed that the complement of the emptiness problem for TMs
(ie, checking whether a given TM accepts any string) is
recognizable (algorithm using a 'dovetailing' technique).
Reading: 4.1. HW5 due. HW6 out.
- Lecture 17 (3/28) Proved that L is decidable
if and only if both L and its complement are
recognizable. Proved that the class of decidable languages
is closed under complement, and mentioned (without proof)
that it is also closed under union, intersection,
concatenation, Kleene star.
Brief overview of what is coming up: we'll prove that there
exist languages that are not recognizable (in fact, most
languages are not). Then we'll show a specific example
language (arguably contrived) that is not decidable, and
not even recognizable. Then we'll show many natural and
important languages that are not decidable, or even not
Defined when a
set is countble (when it is finite, or has the same
cardinality as the naturals, namely there's a bijection
from the naturals to the set). Every subset of a countable
set is countable. Examples of countable sets: negative
integers, even integers, rationals, the set of all strings
over a given alphabet, any one language, the set of all TMs,
the set of all python programs, the set of all
recognizable languages, the set of all decidable
languages. Next, proved that the set of all languages
over a given alphabet (ie., the power set of the set
of all strings) is uncountable. Proof via Cantor's
diagonalisation argument (which can also be used to prove
the set of real numbers, the set of infinite strings, the
power set of any countable set, are all uncountable).
As a corollary of the fact that there are countably many
TMs (algorithmic solutions) and uncountably many languages
(decision problems), we get that there are (uncountably
many) languages that are not recognizable (problems that
are not solvable).
We defined the language X_TM (all encodings of a TM M
such that M, when run on its own encoding as input, does
not accept). We proved that X_TM is not deicidable (same
proof can be used to prove that it's not recognizable),
via the "barber paradox" proof (not really a paradox).
Reading: 4.2 (the textbook has a slightly different
presentation than ours, in particular it doesn't
explicitly define X_TM, but the proof that X_TM
undecidable is given implicitly as part of the proof that
A_TM is not decidable).
- Lecture 18 (3/30) X_TM is not recognizable
(same proof from last class works, and we also showed how
the proof follows a diagonalization argumet). Used that to
prove that A_TM is not decidable (but it is recognizable,
as we've seen before). Concluded that the complement of
A_TM is not recognizable. Proved that HALT_TM ("the
halting problem") is not decidable (but yes
recognizable). Discussion and some further
examples. Discussed the general reduction technique we've
been using to prove decidability and non-decidability,
defined Turing reductions. If A is Turing-reducible to B
and B is decidable, then A is decidable. If A is
Turing-reducible to B and A is not decidable, then B is
not decidable. Recast our previous proofs this lecture in
terms of Turing reductions (we showed X_TM is Turing
reducible to A_TM, and A_TM is Turing reducible to
HALT_TM). Reading: 4.2, 5.1 (beginning), 6.3. See also
poem-proof for undecidability
of the halting problem (basically by reduction to X_TM and
the paradox proof) -- see credits under links below.
- Lecture 19 (4/4)
Review of Turing reductions and their use. Several
examples of languages that are not decidable (E_TM, EQ_TM,
REG_TM), proved via Turing reductions. Stated Rice's
theorem and discussed its implication of undecidability
of basically any non-trivial problem trying to analyze
anything about the input-output behavior of a program.
Reading: 5.1 (upto "computation histories"), Problem 5.28
(and its solution). HW7 out.
- Lecture 20 (4/6)
Proof of Rice's theorem. Examples of problems that can
be proved undecidable using Rice's theorem. Examples
of problems (decidable and undecidable) to which Rice's
theorem can't be applied, as they are not a property of
recognizable languages (e.g., the set of all TMs that
satisfy some property which depends on the actual
implementation, not only on the language of the input TM).
Summarized techniques we've seen so far to prove
undecidability and unrecognizability, and reviewed some of
the examples we've seen (in particular, X_TM,
complement(A_TM), E_TM are all non-recognizable, and we've
seen many examples of undecidable languages). Explained
why a Turing reduction from a non-recognizable language A
to L is not sufficient to prove that L is
non-recongizable. But it is sufficient in the special
case where the reduction calls the decider for L just once
and outputs the same thing -- this special case is
equivalent to a mapping reduction. Defined a mapping
reduction and stated all the following (for now without
proof): If A is mapping reducible to B, then A is Turing
reducible to B (and if A is Turing reducible to B via a
reduction that calls the oracle once and outputs the
same, then A is mapping reducible to B). If A is mapping
reducible to B and B is recognizable, then A is
recognizable. If A is mapping reducible to B and A is
non-recognizable then B is non-recognizable.
Reading: Problem 5.28 and its solution (Rice's theorem),
5.3, 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 6.3.
- Lecture 21 (4/11), given by Flora Min Jung Park:
Reviewed mapping reductions and their relation to
Turing reductions. Proved the two theorems from the end
of last lecture. Proved that if A is mapping reducible to
B then complement(A) is mapping reducible to
compelement(B). Discussed how to use mapping reductions to
prove unrecognizability, and other properties of mapping
reductions. As an example, proved that EQ_TM is neither
recognizable nor co-recognizable. We showed one direction
via a mapping reduction from E_TM (basically noting that
the Turing reduction from E_TM to EQ_TM that we have
already seen before is actually a mapping reduction). We
showed the other direction via a mapping reduction from
complement(A_TM) (that is, a mapping reduction from
complement(A_TM) to complement(EQ_TM), or equivalently, a
mapping reduction from A_TM to EQ_TM).
We revisited the proof of Rice's theorem, noting that it
actually involved a mapping reduction from A_TM, thus
yielding a refined version of Rice's theorem: For any
non-trivial property P of recognizable languages, if the
empty set satisfies P then P is non-recognizable, and if
the empty set does not satisfy P then complement(P) is not
recognizable. Used this refined version to conlude that
CFL_TM is not recognizable.
Reading: See Flora's
lecture notes, as well as chapter 5.3 in the textbook.
- Lecture 22 (4/13)
Wrapping up the computability portion of class, gave a high
level overview (with most formal definitions and proofs
omitted) of reductions using computation histories and
their applications for undecidability of various
probelms. Definition of an accepting computation history
of M on w. M accepts w if and only if there exists an
accepting computation history of M on w. ALL_CFG is
undecidable: sketched the proof by reduction from A_TM,
via computation history technique. EQ_CFG is undecidable
(by reduction from ALL_CFG, proof left as an exercise).
Post's correspondence problem (PCP): described the problem,
and noted that it is undecidable, again via a reduction
from A_TM with a computation history technique (no details
given). The set of ambiguous CFGs is undecidable, by a
reduction from PCP (no details). Many other languages in
various domains can be proven undecidable by a reduction
from PCP or from A_TM using the computation history
technique, including Hilbert's 10th problem, and Church's
result (relying on Goedel's work) that
(informally) there is no algorithm deciding whether a
theorem about number theory is true or false (no details
given even about the precise statement of this).
Introduction and motivation for complexity theory. Review
of big-oh notation. Defined running time of a machine, the
langauge class Time(t(n)), and P (polynomial time
Reading: Def 5.5, Theorem 5.13 (we sketched the proof),
7.1, 7.2 (beginning).
We also superficially touched on the material in 5.2 and
6.2 but you're not responsible for this material. HW7
due. HW8 out.
- Lecture 23 (4/18)
Discussed the class P and its robustness to the details of
the computational model and input representation (for
"reasonable" choices). The strong Church-Turing
thesis. Example of a language in P (all graphs containing a
simple cycle), and many other examples without a proof
(including standard operations on numbers, some problems
on graphs, sorting, regular and context free languages).
Showed that the "grade-school" algorithm for testing
whether a number is prime or composite runs in exponential
time, but mentioned that there is a more sophisticated
poly time algorithm (so these problems are in P).
Emphasized that the running time is measured in terms of
the length of its inputs, so for numbers (represented in
binary say) the running time should be polynomial in the
number of bits it takes to represent the number (which is
logarithmic in the magnitude of the number).
Defined NP, the class of problems for which a correct proof
(aka certificate or witness) can be verified in polynomial
time. Showed that the language of composite numbers is in
NP (via a very simple grade-school level verification
algorithm). This is harder to show for primes (it is true
that the language of primes is in NP as well, in fact it
is in P, but the algorithm is complex). Defined the
complexity class EXPTIME (EXP) and mentioned that P is a
subset of NP, which is a subset of EXP.
Reading: 7.1, 7.2, 7.3.
- Lecture 24 (4/20)
Review of P, NP, EXP, and proof that P is a subset of NP
and NP a subset of EXP. Mentioned (without proof) that we
know that P is a proper subset of EXP, but we don't know
where NP fits in (could be equal P, equal NP, or in
between). Showed that HAM_CYCLE is in NP, and also showed
that it's in EXP. We don't know whether it is in P (the
answer is yes if and only if P=NP). Discussed the P vs NP
problem and its implications. Proved that P is closed
under complement. Discussed why a similar proof does not
work for NP -- in fact, we do not know whether or not NP is
closed under complement (even assuming P not equal NP we
still don't know). Defined poly time reductions. Defined
NP-hard languages and NP-complete languages. If A is poly
reducible to B and B is in P, then A is in P. If A is
poly reducible to B and B is in NP, then A is in NP. If A
is poly reducible to B and A is NP-hard, then B is
NP-hard. Transitivity of poly time reductions (quick
sketch of proof). If A, B are both NP complete then A is
poly reducible to B and B is poly reducible to A. If L is
NP-complete then L is in P if and only if P=NP.
Reading: 7.3, 7.4. See also this
non-technical video about the P vs NP problem. HW8 due.
- Lecture 25 (4/25)
Review of NP completeness (and how it relates to P, NP, NP
hardness). Defined the language SAT, showed it's in NP,
and claimed (for now without proof) that it is NP complete.
Defined CNF-SAT and 3SAT and showed that there's a
reduction from SAT to CNF-SAT and from CNF-SAT to 3SAT
(hence, since all of these are also in NP, all of these
are NP complete). Defined the class NTIME(t(n)). Proved that
NP is equal to the union of NTIME(n^k) for all k (namely,
the class NP of polynomially verifiable languages is the
same as the class of all languages that are decidable in
polynomial time by a non-deterministic TM).
Recalled that NTM are equivalent to (deterministic) TMs via
a transofrmation with an exponential overhead in running
time, and that whether or not there is a transformation
with a polynomial overhead is exactly the P vs NP
problem. Discussed how, even if P is not equal NP (as we
believe), NTM do not violate the strong CT thesis, since
arguably this is not a reasonable model of computation.
Reading: 7.3, 7.4. HW9 out.
- Lecture 26 (4/27)
Sketched the proof of the Cook-Levin theorem, showing that
SAT is NP-complete. Discussed decision vs search vs
optimization problems and some examples.
Showed that if you had a way to solve SAT (answer whether or
not any given formula is satisfiable), you could use it to
find a satisfying assigment if one exists.
More generally, we mentioned that search and optimization
problems have decision versions such that if we can solve
all the decision versions in polynomial time, then the
search / optimization version will also be solvable in
poly time. In particular, for any NP-complete problem, solving
the problem (ie deciding the language) in polynomial time
will allow us to find the certificate in polynomial time.
Thus, the P vs NP problem is the same even if we don't
focus only on decision problems (languages). However,
there are problems that are not NP complete, for which the
natrual search (find the certificate) or optimization
version is believed to be harder than the decision
Discussed the example of factoring -- given a number, find
its factorization. This problem is believed to be
hard (not in P), and much of the cryptography in use today
relies on this (solving it in P would break the
cryptographic scheme). However, the natural decision
version -- given a number, find out if it is composite -- is
in P. But other decision versions of factoring are as
hard as the search version (e.g., given numbers m,k, does
m have a factor less than k). While factoring is in NP
and is believed to be not in P, it is also believed to be
not NP-complete. One reason is that it is in NP intersect
co-NP (ie both the problem and its complement are in NP)
and it is believed that there are no NP complete languages
that are also in co-NP.
Discussed (briefly) ways people approach NP hard problems in
practice: solving it for special cases, particualr input
distributions, heuristics that work a lot of the time even
if not always; Approximation algorithms.
Wrapped up the class and discussed what are the "next
classes" continuing this one
(see some below).
Reading: 7.4 (plus additional discussion not in the text).
HW9 due 5/2.
Handouts with problems covered in practice sessions are posted on
(1/28) Sat 2:00pm-3:30pm in Mudd 833 - Anand Sundaram
(2/5) Sun 1:00pm-2:30pm in Mudd 633 - Rudra Gopinath
(2/11) Sat 2:30pm-4:00pm in Mudd 633 - Cindy Wang
(2/19) Sun 2:30pm-4:00pm in Mudd 627 - Ethan Liu
(2/25) Sat 2:00-4:00pm in Mudd 833 - Anand Sundaram - (Same material as 2/26 session)
(2/26) Sun 1:00-3:00pm in Mudd 633 - Rudra Gopinath - (Same material as 2/25 session)
(3/26) Sun 6:00-7:30pm in Mudd 227 - David Rincon-Cruz
(4/1) Sat 2:30-4:00pm in Mudd 627 - Hidy Han
(4/7) Fri 5:00-6:30pm in Mudd 644 - David Rincon-Cruz
(4/16) Sun 2:00-3:30pm in Mudd 825 - Steven Shao
(4/23) Sun 1:30-3:00pm in Mudd 627 - Jiahui Liu
- (5/3) Wed 1:30-3:30pm in Math 207 -- Luke
Kowalczyk - (Same material as 5/4 session)
- (5/4) Thur 11:00am-1:00pm in Math 207 --
Frederick Kellison-Linn - (Same material as 5/3 session)
Each homework is due electronically through Courseworks. Homeworks must be typed or legibly written and scanned. LaTeX is preferred. The electronic submission should be a single pdf file named after your UNI: [UNI].pdf
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
The midterm will be in class on Thursday March 2nd. It is a closed book exam, with two double sided "cheat sheets" allowed.
The final will take place during finals week, on Tuesday, May 9th,
at 9:30am-11:30pm (for both sections).
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.
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. 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.
Related courses and links
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.
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
- COMS W4236: Introduction to Computational Complexity
- CSOR W4231: Analysis of Algorithms
- COMS W4261: Introduction to Cryptography
- COMS W4252: Introduction to Computational Learning Theory.
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.
- EECS 4340: Computer Hardware Design, and CSEE E4823:
Advanced Logic Design.
Java Formal Languages and Automata Package (JFLAP)
is a useful Java tool that allows you to build automata, test out
their functionality, and easily modify them.
TikZ is a TeX package for programmatically creating graphics which can be used to draw automata. See an example here or here.
GasTeX is a LaTeX plugin for easily drawing finite automata and
graphs. See also
JasTex, a small Java applet for visually drawing finite automata.
It automatically generates GasTeX code.
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).
- Notes on the Myhill-Nerode Theorem
written by TA Michael Tong (not required but highly
- Turing's paper "On
Computable Numbers", published 1936 (possibly more
readable font for the symbols
- 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
Can Name the Bigger Number?: An essay by Scott
Aaronson, related to uncomputability and Turing Machines
(read about the Busy Beaver problem, and more).
- youtube videos informally introducing the complexity
classes P and NP and the implications of the P vs NP problem:
- Surveys about P vs NP problem, significance, and
progress (varying levels of technical details, perspectives, and
Scott Aaronson, 2016
Philosophers Should Care About Computational Complexity
by Scott Aaronson, 2013
Creativity and P vs NP (a very informal draft) Avi
P, NP and Mathematics - A Computational Complexity
Perspective Avi Wigderson, 2006 (appeared in proceedings
of the International Congress of Mathematicians, Madrid)
P versus NP Problem Stephen
Cook, 2000 (written for the announcement of the Clay
- The History and Status of the P
versus NP Question Michael Sipser, 1992. The appendix
includes the original letter from Kurt Gödel
to John von Neumann
(in German), as well as a translation.
- Interesting historical documents:
- a letter from John
Nash to the NSA in 1955 (declassified in 2012), regarding a
cryptosystem that he proposed. In this
letter Nash foresees fundamental aspects of modern
cryptography and provable security, along the way clearly
discussing polynomial time vs expolnential time and the
difficulty of proving that a certain problem is in
exponential time -- this is more than a decade ahead of the time these
ideas (and P vs NP) came up in computational complexity.
Original (hand-written but very legible), and
(transcribed by Rosulek).
- a letter from Kurt Gödel to John von Neumann
from 1956, essentially stating the P vs NP problem -- this
is, again, more than a decade ahead of the time this
question was posed in computational complexity.
The original in German (as well as a translation to English)
can be found in the appendix of Sipser's survey, and there's also a
translation on Lipton's