CS 39 (Winter 2015): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Winter 2015

[ 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 7] The midterm exam has been posted. Click on the link in the schedule table.
[Jan 5] We will be using Piazza for all class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com. Here is our class page on Piazza.
[Jan 5] 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 | 2 hour | Mon-Wed-Fri 13:45-14:50, X-hr Thu 13:00-13:50

Instructor

Amit Chakrabarti
Sudikoff 107 | 646-1710 | Office hours: Mon 15:00-16:00, Tue 13:00-14:00, or by appointment

Teaching Assistants

Jack Holland
Sudikoff 152 | 914-400-9223 | Office hours: Wed 15:00-16: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 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 5	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
	2	Jan 7	0.1, 0.2, 0.3	—	Types of proof (direct, contradiction, induction) (slides)
	3	Jan 8 x	0.4	—	Strings and languages; Finite automata; Basic DFA examples
	4	Jan 9	1.1 up to p34	—	Further DFA examples; formalization as (Q,Σ,δ,q₀,F)

Week 2	5	Jan 12	1.1	—	Formalization of DFA computations; Closure under union/intersection
	6	Jan 14	1.2	—	The regular operations; Regular expressions
	7	Jan 15 x	—	HW1	Kleene's Theorem; Conversion of RegExp to NFA; (lecture notes);
	8	Jan 16	1.3 up to p69	—	Kleene's Theorem II: Conversion of NFA to DFA;

Week 3		Jan 19	—	—	No class; MLK day
	9	Jan 21	1.3	—	Kleene's Theorem III: of DFA to RegExp (lecture notes)
	10	Jan 22 x	1.4	HW2	The pumping lemma; proving non-regulartiy
	11	Jan 23	Chapter 1	—	Non-regularity via pumping lemma and closure properties

Week 4		Jan 26	—	—	Quiz 1: closed-notes, in-class
	12	Jan 28	2.2 up to p116	—	Pushdown automata; Examples
	13	Jan 29 x	—	HW3	Formal definition of a PDA; More examples
	14	Jan 30	2.1 up to p108	—	Context-Free Grammars (CFGs); Examples; Formal definitions; Ambiguity

Week 5	15	Feb 2	2.1	—	CFG for N₀ = N₁ (lecture notes)
	16	Feb 4	—	—	Equivalence of CFGs and PDAs (lecture notes)
	17	Feb 5 x	2.2	—	Pumping lemma for CFLs; Applications
		Feb 6	2.3	HW4	No class: Winter carnival

Week 6	18	Feb 9	3.1	—	Proof of the CFL pumping lemma; CFL wrap-up
	19	Feb 11	—	—	Turing machines (palindromes, adder)
	20	Feb 12 x	—	Midterm	Formal description of TMs; Deciders/recognizers; Implementation Descriptions
	21	Feb 13	3.1	—	Multi-tape TMs; Equivalence with single-tape TMs (slides)

Week 7	22	Feb 16	3.2 up to p150	—	Nondeterministic TMs; The RAM model; Church-Turing Thesis (slides); Enumerator TMs
	23	Feb 18	Chapter 3	—	Decision problems for major language classes: Decidability of A_DFA, A_CFG; Recognizability of A_TM
	24	Feb 19 x	4.1	HW5	Undecidability of A_TM
	25	Feb 20	Chapter 4	—	Decidability of E_DFA, ALL_DFA, EQ_DFA, E_CFG; Mapping reductions; Unrecognizability of E_TM

Week 8		Feb 23	5.1 up to p192; 5.3	—	Quiz 2: closed-notes, in-class
	26	Feb 25	—	—	Further reductions; Unrecognizability of EQ_TM; Discussion of ALL_TM, INT_TM
	27	Feb 26 x	7.1	—	Time complexity, P and NP
	28	Feb 27	7.1 – 7.3	HW6	NP-completeness and polynomial time reductions (slides)

Week 9	29	Mar 2	TBD	—	More NP-completeness proofs: IND-SET, CLIQUE, UHAMCYCLE
	30	Mar 4	TBD	—	Yet more NP-completeness: TSP, 3-COL
	31	Mar 5 x	—	—	Tractability of 2-COL, 2-SAT; Computational tableaux
	32	Mar 6	—	—	Undecidability of INT_CFG

Week 10	33	Mar 9	TBD	HW7	Unrecognizability of ALL_CFG; The Cook-Levin Theorem

Deadline Mar 14					Take-home 48-hour final exam, due at 5:00pm sharp

Lectures	Sudikoff 115 \| 2 hour \| Mon-Wed-Fri 13:45-14:50, X-hr Thu 13:00-13:50
Instructor	Amit Chakrabarti Sudikoff 107 \| 646-1710 \| Office hours: Mon 15:00-16:00, Tue 13:00-14:00, or by appointment
Teaching Assistants	Jack Holland Sudikoff 152 \| 914-400-9223 \| Office hours: Wed 15:00-16: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