CS 39 (Winter 2012): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Winter 2012

[ Announcements | Administrative Basics | Schedule and Homeworks | Solutions | Grades Database ]

Course Description

This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, context-free languages, pushdown automata, Turing machines, computability, and NP-completeness.

This course has substantial mathematical content. It is expected that a student who enrols for this course already knows how to write mathematical proofs and is generally mathematically mature. If a student passes this basic criterion and is interested in thinking philosophically about what a computer can or cannot do, then this course should be great fun.

Announcements

[Mar 15] The final exam website is now closed. Numerical scores for the final will be in the grades database by ~~Mar 16 night~~ Mar 17 afternoon (sorry about the delay; since several solutions got rather creative, I need a little more time to grade everything with the care it deserves).
[Mar 07] The final exam is ready. Do click through to read the instructions. Your clock does not start until you download the exam.
[Feb 13] From now on, it will be especially important to keep up with the reading from the textbook that is marked on the schedule table below, as the course starts to accelerate its pace.
[Feb 5] The midterm has been posted.
[Jan 16] Although we did not have class today, Homework 2 has been posted to course website on schedule. It is due before next Monday's class.
[Jan 03] Please send email to the professor (Amit Chakrabarti) with your name (only first and last name, no initials) and a password for accessing your grades in our database.

Administrative Basics

Important! Please also read and familiarize yourself with the administrative details not covered in the outline below. Pay special attention to the section that describes how the honor code applies to this course; violations of the honor code will be treated seriously.

Lectures

Sudikoff 214 | 11 hour | Mon-Wed-Fri 11:15-12:20, X-hr Tue 12:00-12:50

Instructor

Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Mon 9:00-10:30, Fri 13:30-14:30, or by appointment

Teaching Assistant

Thomas Bao | Sudikoff 212 | (phone TBA) | Office hours: Mon 16:00-17:00, Tue 16:00-18:00, or by appointment

Textbook

Required:
"Introduction to the Theory of Computation," Second Edition. Michael Sipser.
Suggested additional reading (not required):
"Introduction to Automata Theory, Languages and Computation." J. E. Hopcroft and J. D. Ullman.

Prerequisites

Either CS 30 or CS 31, or
a strong mathematics backround and permission of the instructor

Work

One homework per week. [35 points]
Two in-class quizzes. [15 points]
One take-home midterm. [20 points]
One take-home final exam. [30 points]

Please take note of the late homework policy. It will be enforced, strictly.

Schedule and Homeworks

This schedule will be updated frequently. Please check back often, and please remember to hit the RELOAD button to get the latest schedule.

Any part of the schedule that is greyed out is tentative and subject to change.

Lecture Number and Date			Reading Due Before Class	Homework Due	Topics Covered in This Lecture

Week 1	1	Jan 4	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
Week 1	2	Jan 6	0.1, 0.2, 0.3	—	Types of proof: by construction, by contradiction, by induction (slides)

Week 2	3	Jan 9	0.4	—	Strings and languages; Finite automata; DFA examples (slides)
	4	Jan 10 (X-hr)	1.1 up to p34	—	Formal definition of DFA as (Q,Σ,δ,q₀,F); More DFA examples
	5	Jan 11	1.1	—	NFA introduced; Examples; Formalization of NFAs and DFA/NFA computation
	6	Jan 13	—	—	More on NFAs; The union, concatenation and Kleene star operations

Week 3		Jan 16	—	HW1	No lecture: MLK Day
	7	Jan 17 (X-hr)	1.3 up to p69	—	Regular expressions, examples, conversion to NFA (lecture notes)
	8	Jan 18	—	—	Equivalence of DFAs, NFAs and regular expressions, I
	9	Jan 20	1.2	—	Equivalence of DFAs, NFAs and regular expressions, II (lecture notes)

Week 4	10	Jan 23	1.3	HW2	The pumping lemma and proofs of non-regularity
	11	Jan 24 (X-hr)	1.4	—	Closure properties of regular languages
	12	Jan 25	Chapter 1	—	Pushdown automata; Examples of PDAs
		Jan 27	—	—	Quiz 1: closed-notes, in-class

Week 5	13	Jan 30	—	HW3	Formal definition of a PDA; More examples; Closure under ∪, ∘, *
	14	Jan 31 (X-hr)	2.2 up to p115	—	Context-Free Grammars (CFGs); Basic examples
	15	Feb 1	2.1 up to p105	—	Formal definition of a CFG; Ambiguity; CFG for N₀ = N₁ (lecture notes)
	16	Feb 3	—	—	Equivalence of CFGs and PDAs, I: PDA to CFG

Week 6	17	Feb 6	—	HW4	Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
	18	Feb 7 (X-hr)	—	—	Chomsky Normal Form; Pumping lemma for CFLs
	19	Feb 8	2.2	Midterm	Applications of CFL pumping lemma and closure properties
		Feb 10	—	—	No lecture: Winter Carnival

Week 7	20	Feb 13	Chapter 2	—	Turing machines; formal description; demos (palindromes, adder)
	21	Feb 14 (X-hr)	3.1	—	Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
	22	Feb 15	3.2 up to p150	HW5	Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)
	23	Feb 17	Chapter 3	—	Enumerator TMs; Decision problems for the major language classes: A_DFA, A_CFG and A_TM

Week 8	24	Feb 20	4.1	—	Decidability of A_DFA, A_CFG; Recognizability of A_TM; Undecidability of A_TM
	25	Feb 21 (X-hr)	Chapter 4	—	Reductions; Mapping reductions; Decidability of E_DFA, ALL_DFA, EQ_DFA; Undecidability of ALL_TM
	26	Feb 22	5.1 up to p192; 5.3	HW6	Unrecognizability of A_TM, E_TM; Decidability of E_CFG
		Feb 24	—	—	Quiz 2: closed-notes, in-class

Week 9	27	Feb 27	7.1	—	Time complexity, P and NP
		Feb 28 (X-hr)	7.1 – 7.3	—	NP-completeness and polynomial time reductions (slides)
	28	Feb 29	TBD	HW7	More NP-completeness proofs: IND-SET, 3-COL
	29	Mar 2	TBD	—	Yet more NP-completeness: CLIQUE, TSP; Tractability of 2-COL, 2-SAT

Week 10	29	Mar 5	—	—	Computational tableaux; Unrecognizability of ALL_CFG
	30	Mar 6 (X-hr)	—	—	Undecidability of INT_CFG
	31	Mar 7	7.4 up to p276; 7.5	HW8 (optional)	The Cook-Levin Theorem; Wrap-up

Mar 14			Take-home 48-hour final exam, due at 5:00pm sharp The final exam website is now closed.

Solutions to Homework and Exam Problems

These will be provided in class, when graded homeworks are given out. Hard-copy only.

Grades Database

If you are a registered student, you may verify your grades as entered in our database using the form below.