COMS W3261: Computer Science Theory, Spring 2012

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

The course is from 2:40 to 3:55 on Tuesday and Thursday, in 312 Math.

• (5/12) Final exam grades have been uploaded to courseworks (see announcement there for statistics). Final grades submitted for graduating seniors, will be submitted for the rest of the students in the next few days. If you enjoyed the class, be sure to check out some other theory classes. Have a wonderful summer!

All TA office hours are in the Computer Science TA room in Mudd. All of Professor Malkin's office hours are in 514 CSB. If you do not have swipe access to the computer science building, please ask someone in the office to let you in.

Week of 4/30 - 5/4

• Monday
  • Jacob 3-5
• Tuesday
  • Jacob 10-11:30
  • Prof. Malkin 2:30-5:30
• Wednesday
  • Prof. Malkin 9-10
  • Emma 10-12
  • Will 12-2
• Thursday
  • Emma 9-10
  • Will 10-11:30

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 1 (1/17) Motivation and overview of the class. Definitions of alphabet, strings and languages. Examples and definition of DFA and language recognized by a DFA. Readings: Chapter 0, 1.1. Homework 1 posted.
• Lecture 2 (1/19) Review of DFA and Regular languages. All finite languages are regular. More examples of (infinite) regular languages. Started NFA (an example and informal definition). Readings: Chapter 1.2
• Lecture 3 (1/24) Definition of NFA, its computation tree, and the language recognized by it. Examples. Every NFA has an equivalent DFA (subset construction): intuition and example. Readings: Chapter 1.2. Homework 2 posted.
• Lecture 4 (1/26) The subset construction converting an NFA to an equivalent DFA. Discussion on the number of states: the exponential gap is inherent (showed a language that exhibits this gap, but did not prove the lower bound). Definitions of some operations on languages (including complement, union, concatenation, power, Kleene star, symmetric difference). Stated that the class of regular languages is closed under these operations, and proved it for complement. Readings: Chapter 1.2. Homework 1 due.
• Lecture 5 (1/31) The class of regular languages is closed under regular operations (union, concatenation, star). Definition of regular expressions and the languages they describe. A language is regular if and only if it can be generated by a regular expression (proved the "if" direction). Readings: Chapter 1.3.
• Lecture 6 (2/2) Examples of regular expressions and the transformation from a regular expression to an equivalent NFA. Completed the equivalence proof by showing the transformation from a DFA to an equivalent regular expression. Began discussion of non-regular languages. Reading: Chapter 1.3,1.4. Homework 2 due.
• Lecture 7 (2/7) Pumping Lemma: proof and examples. Example applications of pumping lemma and closure properties to prove non-regularity. Reading: Chapter 1.4. Homework 3 posted.
• Lecture 8 (2/9) Context free grammars: definitions, examples, ambiguity. Reading: Chapter 2.1.
• Lecture 9 (2/14) Proved CFL are closed under regular operations. Proved that every regular language is context free, by showing a CFG for every regular expression. Defined "regular grammars" where each rule is of the form A → aB or A → a or A → ε. Proved that a language is regular if and only if it has a regular grammar (showed how to transform a DFA to a regular grammar; other direction is similar). Pushdown Automata (PDA): Definition and example. Reading: Chapter 2.1,2.2. Homework 3 due.
• Lecture 10 (2/16) PDA: more examples; L is a CFL if and only if it is recognized by a PDA (proved only one direction, CFG to PDA transformation); Tandem pumping lemma for context free languages (without proof) and its use to prove a language is not context free. Reading: 2.2, 2.3. Homework 4 posted.
• Lecture 11 (2/21) CFL are not closed under intersection, nor under complement. CFL wrap up, discussion, roadmap, introduction to general computability and Turing Machines. TM definitions (machine, configurations, recognized language, decider, TM-recognizable and TM-decidable languages). Reading: 3.1.
• Lecture 12 (2/23) TM overview and discussion. A complete example (full state diagram and all configuration of example computations). Definition and example of input-output TM and computable functions. Reading: 3.1,3.2. Homework 4 due. Homework 5 posted.
• Lecture 13 (2/28) Definition of a computable function. Examples. Multi-tape TM and non-deterministic TM, and their equivalence to standard TM.
• Lecture 14 (3/1/12) Church-Turing Thesis (history, statement, implications). Proved that L is decidable if and only if L and its complement are both recognizable. Universal TM. Proved decidability of acceptance problem for DFAs and NFAs and emptiness problem for DFAs. Reading: 3.3, 4.1. Homework 5 due.
• Midterm: in class, 3/6/12
• Lecture 15 (3/8/12) Proved equivalence problem for DFAs is decidable. Discussed (without proof) how acceptance and emptiness for CFG are also decidable. Mentioned (without proof) that equivalence problem for CFG is not decidable, and checking ambiguity of a CFG is not decidable. Proved that the acceptance problem for TM (A_TM) is recognizable (by the universal TM). Review of definition and examples for countable and uncountable sets, and diagonalization method. Set of (finite) strings and set of TMs are both countable. Set of languages is not countable (by diagonalization). Thus, there exists a language that is not TM-recognizable. Defined X_TM and proved it is not decidable. Reading: 4.2
• Spring break 3/12/12 - 3/16/12
• Lecture 16 (3/20/12) Reviewed uncountability of languages, undecidability of X_TM. Proved the undecidability of A_TM, HALT_TM, E_TM, REG_TM. Defined and discussed Turing reductions and their use to prove undecidability. Jacob's lecture notes. Reading: 4.2, 5.1 (first half), 6.3. Homework 6 posted.
• Lecture 17 & 18 (3/27/12 & 3/29/12) Review of Turing reducibility. Using reductions to prove decidability of languages. Using reductions to prove undecidability. Rice's theorem. Some examples for which we proved undecidability: EQ_TM, ALL_TM, CFG_TM. Briefly discussed (without proof) some examples of undecidable problems that do not look like general TM questions: Hilbert's 10th problem (integral roots for Diophantine equations), Post's correspondence problem, ambiguity of a CFG, first order logic theorems. All these can be proved by reduction from A_TM using computation history technique. Reading: 5.1, 6.3, Problem 5.28. HW 6 due. HW7 posted.
• Lecture 19 (4/3/12) Methods for proving a language is not recognizable: If L is recognizable but not decidable, complement(L) is not recognizable (Example: E_TM is not recognizable). Definition of Mapping reductions ("question converters"). Mapping reduction implies a Turing reduction where the oracle/subroutine is used just once and its output is used as the output of the program. A is mapping reducible to B if and only if complement(A) is mapping reducible to complement(B). If A is mapping reducible to B and B is recognizable, then A is recognizable. Cor: if A is mapping reducible to B and A is not recognizable, B is not recognizable. Examples: EQ_TM is neither recognizable nor co-recognizable. A few words on Alan Turing (his contributions to computer science, defeating the nazis in world war II, and his personal life and tragic end). Reading: 5.3
• Lecture 20 (4/5/12) Intro to complexity theory: defined running time of a machine, the classes Time(t(n)), P (polynomial time computable), EXP (exponential time computable), NP (polynomial time verifiable). The strong Church-Turing thesis. Examples: simple cycle is in P, composites is in NP (mentioned without proof that it's actually in P). Reading: 7.1, 7.2, 7.3. HW7 due. HW8 posted.
• Lecture 21 (4/10/12) Review of P, NP. Definition of polynomial reduction. If A is polynomially reducible to B and B is in P, then A is in P. Definition of NP completeness and NP hardness. If B is NP hard and B polynomially reducible to C, then C is NP hard. Examples (Hamiltonian cycle, etc - there are very many). Equivalent characterization of NP via polynomial time non-deterministic TMs. Discussion of P vs NP and its significance, state of what we know and what we conjecture about the complexity classes P, NP, co-NP, NP-Complete, EXP. Reading: 7.4
• Lecture 22 (4/12/12) Examples of languages in NP that are believed to not be in P, nor NP-complete: Graph isomorphism, Bounded factor. Decision vs search problems (bounded factor in P implies finding a factor for a given number is in P). NP Complete languages: {(M,w,1^t): M is a NTM that accepts w in at most t steps}; CNF-SAT is NP Complete (Cook-Levin theorem), with proof sketch. HW8 due.
• Lecture 23 (4/17) NP completeness review. Proved NP completeness of SAT, 3SAT, Independent_set, and Clique. Reading: Chapter 7
• Lecture 24 (4/19) Subset sum is NP complete. P vs NP discussion. Probabilistic TMs, definition of RP and co-RP, amplification of success probability for RP, Identity testing in RP. Reading: 7.5, 10.2. HW9 posted.
• Lecture 25 (4/24) Reviewed randomized computation (including motivation and discussion on randomness in computation). Claimed (without proof) that 2SAT is in P, and showed a simpler randomized algorithm showing 2SAT is in RP. Defined BPP, amplification of success probability for BPP. Defined ZPP ("Las-Vegas" algorithms vs RP and BPP that are "Monte-Carlo" algorithms). Discussed known relationships among these classes (and P, NP, EXP). All proofs were only sketched (or skipped). Brief overview introducing approximation algorithms. Reading: 10.2
• Lecture 26 (4/26) Final review. Final covers everything in the computability and complexity parts of the class (mid lecture 11 -- end). Students are responsible for all material covered in class. Closed book exam, two double-sided sheets allowed. HW9 due.

Handouts with problems covered in recitation are posted on courseworks.

• Recitation 1 (Fri 1/27, 3:00 - 4:30) Taught by Jacob Andreas. Room: 207 Math.
• Recitation 2 (Fri 2/10, 1:30-3:00) Taught by Emma Ziegellaub Eichler. Room: 603 Hamilton.
• Recitation 3 (Fri 2/24, 10:30-12:00) Taught by Kui Tang. Room: 203 Math.
• Midterm Review (Fri 3/2, 10:30-12:00) Taught by Will Brown. Room: 203 Math.
• Recitation 4 (Thur 3/22, 2:40-3:55) Taught by Will Brown. Room: 312 Math.
• Recitation 5 (Wed 4/11, 6:00-7:30pm) Taught by Kui Tang. Room: IAB 255.
• Recitation 6 (Fri 4/20, 3:00-4:30pm) Taught by Emma Ziegellaub Eichler. Room: 633 Mudd.

Each homework is due at the beginning of each class. Homework not submitted at the beginning of class will be considered late. Homeworks must be legibly written or typed. LaTeX is preferred - Jacob has written an excellent list of LaTeX resources on the Courseworks discussion board.

• Homework 1 (Due Thursday 1/26) Problems 0.1 - 0.9 and 0.12 from the textbook. Please note that you are not allowed to collaborate with your classmates on this homework. Graded by Will Brown.
• Homework 2 (Due Thursday 2/2). Updated 1/29 to clarify the language specification in 3.b. Parts I/II graded by Kui Tang/Emma Ziegellaub Eichler, respectively.
• Homework 3 (Due Tuesday 2/14). Parts I/II graded by Will Brown/Jacob Andreas.
• Homework 4 (Due Thursday 2/23). Parts I/II graded by Kui/Emma.
• Homework 5 (Due Thursday 3/1). Note that this homework counts as half. No late homework will be accepted. Graded by Jacob.
• Homework 6 (Due Tuesday 3/27). Parts I/II graded by Emma/Will.
• Homework 7 (Due Thursday 4/5). Parts I/II graded by Jacob/Will.
• Homework 8 (Due Thursday 4/12). Note that this homework counts as half. Graded by Will.
• Homework 9 (Due Thursday 4/26). No late homework will be accepted. Parts I/II graded by Jacob/Emma.

The homework constitutes 15%, Midterm constitutes 40%, and the final constitutes 45% of the final grade. Doing the homework is crucial for understanding and getting comfortable with the material; it is unlikely you will be able to do well on the tests without doing the homework. You are advised to start the homework early.

Lateness policy

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

Collaboration policy

All students are assumed to be aware of the computer science department academic honesty policy . Homework should constitute your own work. Collaboration in groups of two or three students is allowed, but not required. Collaboration in groups of more than three students is not allowed. You should write your own solution, and list the names of all people that you collaborated with. 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, Second Edition by Michael Sipser, PWS Publishing Company. Copies are currently available at the Columbia bookstore, and there are five copies on reserve at the Engineering Library. The book's website and errata are available here. We will generally follow the book in class, but some departures are possible. Students are responsible for all material taught in class.

Optional text: Introduction to Automata Theory, Languages and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman

CS 3261 constitutes the last CS Theory course required to be taken by all CS majors. Students interested in the material covered by this course are strongly encouraged to pursue some of the advanced courses offered in in theoretical computer science. See the theory group's webpage for more information and a list of past and current theory courses. In particular, the following courses are very closely related in spirit to the topics covered in CS 3261:

• COMS W4236: Introduction to Computational Complexity (offered Spring 2013).
• CSOR W4231: Analysis of Algorithms (offered Fall 2012).
• COMS W4252: Introduction to Computational Learning Theory (offered Fall 2012).
• COMS W4261: Introduction to Cryptography (offered Fall 2012).
• COMS W4995: Introduction to Communication Complexity
• COMS E6998-001: Randomness in Computing (offered Fall 2012).
• Several different classes related to graph theory: COMS W3203, COMS W4203, COMS E6998-005, CSOR E4010 (the first three are offered Fall 2012).

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 (offered Fall 2012).
• COMS 4705: Natural Language Processing (offered Fall 2012).
• EECS 4340: Computer Hardware Design, and CSEE E4823: Advanced Logic Design (offered Fall 2012).

Useful links

• 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.
• 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.
• 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).
• Finite State Automation Applet is an automaton simulator, similar to JFLAP. Requires Java.
• 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, with a Belarusian translation here.