CS 39 (Winter 2009): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Winter 2009

[ 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 17] Here are URLs for the two Turing Machine demo applets we saw in class today: TM1 and TM2. Play with them sometime. They'll enhance your understanding.
[Jan 21] Quiz 1 will be based on material covered up to, and including, Lecture 11.
[Jan 21] While working on HW3, note that problems 4.6, 5.3 and 5.6 depend on some material (namely, closure properties) that will get covered a little later. So you might want to work on these particular problems last.
[Jan 09] We now have three TAs. All office hours have been posted; see below.
[Jan 09] Starting today, we have a no-laptop policy in class. This is for the benefit of all, so as to encourage active participation in class by all students.
[Jan 02] Please send a blitz to the instructor with your name (only first and last name, no initials) and a password for accessing your grades in the grades 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

Kemeny 008 | 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 18:00-20:00, Fri 15:00-16:30, or by appointment

Teaching Assistants

Qi (Tracy) Gu | Sudikoff 220 | 6-8752 | Office hours: Fri 16:00-18:00
Grace Moy | Sudikoff 114 | 440-554-0373 | Office hours: Sun 16:00-18:00
William Henderson-Frost | Sudikoff 114 | 817-701-6019 | Office hours: Mon 16:00-18:00

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

CS 25, 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 5	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
	2	Jan 6 (X-hr)	0.1, 0.2, 0.3	—	Types of proof: by construction, by contradiction, by induction (slides)
	3	Jan 7	0.4	—	Strings and languages; Finite automata; DFA examples (slides)
	4	Jan 9	1.1 up to p34	—	Formal definition of DFA as (Q,Σ,δ,q₀,F); More DFA examples

Week 2	5	Jan 12	1.1	—	NFA introduced; Examples; Formalization of NFAs and DFA/NFA computation
	6	Jan 13 (X-hr)	—	—	More on NFAs; The union, concatenation and Kleene star operations
	7	Jan 14	—	HW1	Regular expressions, examples, conversion to NFA (lecture notes)
	8	Jan 16	1.3 up to p69	—	Equivalence of DFAs, NFAs and regular expressions, I

Week 3		Jan 19	—	—	No lecture: MLK Day
	9	Jan 20 (X-hr)	1.2	—	Equivalence of DFAs, NFAs and regular expressions, II (lecture notes)
	10	Jan 21	1.3	HW2	The pumping lemma and proofs of non-regularity
	11	Jan 23	1.4	—	More proofs of non-regularity; Proof of the pumping lemma

Week 4	12	Jan 26	—	—	Closure properties of regular languages (guest lecture)
		Jan 27 (X-hr)	Chapter 1	—	Open/Review session with TAs
		Jan 28	—	HW3	Quiz 1: closed-notes, in-class
	13	Jan 30	—	—	Pushdown automata; Examples of PDAs

Week 5	14	Feb 2	—	—	Formal definition of a PDA; More examples
	15	Feb 3 (X-hr)	2.2 up to p115	—	Closure under union, concatenation and Kleene star; Context-Free Grammars (CFGs); Basic examples
	16	Feb 4	2.1 up to p105	HW4	More advanced CFGs: N₀ = N₁ and non-xx strings (lecture notes)
	17	Feb 6	—	—	Equivalence of CFGs and PDAs, I: PDA to CFG

Week 6	18	Feb 9	—	—	Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
		Feb 10 (X-hr)	2.2	—	Open/Review session with TAs
	19	Feb 11	—	Midterm	Chomsky Normal Form; Conversion Algorithm; Pumping lemma for CFLs (guest lecture)
		Feb 13	—	—	No lecture: Winter Carnival

Week 7	20	Feb 16	2.3	—	Applications of CFL pumping lemma; Closure properties
	21	Feb 17 (X-hr)	Chapter 2	—	Turing machines; formal description; demos (palindromes, adder)
	22	Feb 18	3.1	—	Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
	23	Feb 20	—	HW5	Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)

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

Week 9	27	Mar 2	5.1 up to p192; 5.3	—	Time complexity, P and NP
	28	Mar 3 (X-hr)	7.1	—	NP-completeness and polynomial time reductions (slides)
	29	Mar 4	7.1 – 7.3	HW7	More NP-completeness proofs
	30	Mar 6	—	—	Computation tableaux; The Cook-Levin theorem

Week 10	31	Mar 9	—	—	Cook-Levin theorem continued; Unrecognizability of ALL_CFG
Week 10	32	Mar 10 (X-hr)	7.4 up to p276; 7.5	HW8 (optional)	Wrap-up

Mar 16			Take-home 48-hour final exam, due at 6:00pm sharp The final exam webpage 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.