CS 39 (Winter 2013): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Winter 2013

[ 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

[Feb 19] New office hours have been posted. You might have to refresh this page to see the latest.
[Feb 11] The honor code requirements for homeworks have been updated. The new wording clarifies what you may or may not consult during the learning stage and final draft writing stage, as you work on the homework. Please read and understand the new statement.
[Feb 5] The midterm exam is live. Main advice: start early!
[Jan 8] The class has officially moved to Sudikoff 115.
[Jan 3] 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 115 | 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 09:00-10:30, Tue 10:00-11:00, or by appointment

Teaching Assistant

Keith Carlson
Sudikoff 108 | 6-3297 | Office hours: Wed 10:00-11:00, Thu 14:00-15:00, or by appointment

Textbook

Required:
"Introduction to the Theory of Computation," Third 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 is a work in progress. The dates for the quizzes and the due dates for the homework sets, the midterm and the final exam are now fixed as shown below. This schedule will be updated frequently. Please check back often, and please remember to RELOAD to get the latest schedule.

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

Please be sure to read and understand the Homework Grading Guidelines and the Late Submission Policy.

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

Week 1	1	Jan 7	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
	2	Jan 8 (X-hr)	0.1, 0.2, 0.3	—	Types of proof (direct, contradiction, induction); Strings and languages (slides)
	3	Jan 9	0.4	—	Finite automata; Basic DFA examples
	4	Jan 11	1.1 up to p34	—	DFA formalized as (Q,Σ,δ,q₀,F); Formalization of DFA computations; NFAs; Examples

Week 2	5	Jan 14	1.1	—	Formalization of NFAs and their computation; NFA for L₁∪L₂
	6	Jan 15 (X-hr)	1.2	HW1	Regular expressions; Examples; Conversion to NFA
	7	Jan 16	—	—	Kleene's Theorem I: Conversion of NFA to DFA (lecture notes)
	8	Jan 18	1.3 up to p69	—	Kleene's Theorem II: Conversion of DFA to regular expression (lecture notes)

Week 3		Jan 21	—	—	No lecture: MLK Day
	9	Jan 22 (X-hr)	1.3	HW2	The pumping lemma and proofs of non-regularity
	10	Jan 23	1.4	—	Closure properties of regular languages
	11	Jan 25	Chapter 1	—	Pushdown automata; Examples of PDAs

Week 4	12	Jan 28	—	—	Quiz 1: closed-notes, in-class
		Jan 29 (X-hr)	—	HW3	Formal definition of a PDA; More examples; Closure under ∪, ∘, *
	13	Jan 30	—	—	Context-Free Grammars (CFGs); Basic examples
	14	Feb 1	2.2 up to p115	—	Formal definition of a CFG; Ambiguity; CFG for N₀ = N₁ (lecture notes)

Week 5	15	Feb 4	2.1 up to p105	—	Equivalence of CFGs and PDAs, I: PDA to CFG
	16	Feb 5 (X-hr)	—	HW4	Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
	17	Feb 6	—	—	Chomsky Normal Form; Pumping lemma for CFLs
		Feb 8	—	—	No lecture: Winter Carnival

Week 6	18	Feb 11	2.2	Midterm	Applications of CFL pumping lemma and closure properties
	19	Feb 12 (X-hr)	—	—	Turing machines; formal description; demos (palindromes, adder)
	20	Feb 13	Chapter 2	—	Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
	21	Feb 15	3.1	HW5	Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)

Week 7	22	Feb 18	3.2 up to p150	—	Enumerator TMs; Decision problems for the major language classes: A_DFA, A_CFG and A_TM
	23	Feb 19 (X-hr)	Chapter 3	—	Decidability of A_DFA, A_CFG; Recognizability of A_TM; Undecidability of A_TM
	24	Feb 20	4.1	—	Quiz 2: closed-notes, in-class
	25	Feb 22	Chapter 4	HW6	Decidability of E_DFA, ALL_DFA, EQ_DFA; Decidability of E_CFG; Unrecognizability of A_TM

Week 8	26	Feb 25	5.1 up to p192; 5.3	—	Reductions; Undecidability of Halting problem; Mapping reductions; Unrecognizability of E_TM
		Feb 26 (X-hr)	—	—	Time complexity, P and NP
	27	Feb 27	7.1	—	NP-completeness and polynomial time reductions (slides)
	28	Mar 1	7.1 – 7.3	HW7	More NP-completeness proofs: IND-SET, CLIQUE, UHAMCYCLE, TSP

Week 9	29	Mar 4	TBD	—	Yet more NP-completeness: 3-COL; Tractability of 2-COL, 2-SAT
	30	Mar 5 (X-hr)	TBD	—	Computational tableaux; Unrecognizability of ALL_CFG; Undecidability of INT_CFG
	31	Mar 6	—	—	The Cook-Levin Theorem
	32	Mar 8	—	HW8 (optional)	Wrap-up

Deadline Mar 13 (now live)					Take-home 48-hour final exam, due at 5:00pm sharp

Lectures	Sudikoff 115 \| 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 09:00-10:30, Tue 10:00-11:00, or by appointment
Teaching Assistant	Keith Carlson Sudikoff 108 \| 6-3297 \| Office hours: Wed 10:00-11:00, Thu 14:00-15:00, or by appointment
Textbook	Required: "Introduction to the Theory of Computation," Third 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.

Your name, without initials or suffixes:
Your CS 39 password:

Computer Science 39 Theory of Computation Amit Chakrabarti