CS 39 (Fall 2007): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2007

[ 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

[Nov 25] Important info about the final exam has been posted. Please click the link in the schedule table below.
[Nov 14] Copies of the slides used in Lectures 25 and 27 have been posted to this website. Please see the schedule table.
[Oct 23] Solutions to Quiz 1 have been posted to the course website. Please read them carefully. Also, please do the same for all posted homework and exam solutions.
[Oct 8] We have moved. Starting Oct 9, all lectures and X-hours will be held in Thornton 105 (click the link to see it on the campus map).
[Oct 1] We now have two TAs. Updated contact info and office hours have been posted. Remember, you can always meet one of the course staff outside of scheduled office hours too; just drop by, or send a blitz to arrange for a time.
[Sep 18] 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

Sudikoff 214 | 12 hour | Mon-Wed-Fri 12:30-13:35, X-hr Tue 13:00-13:50

Instructor

Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Wed 17:00-18:00, Sun 14:00-16:00, or by appointment

Teaching Assistants

Umang Bhaskar | Sudikoff 205 | 6-8745 | Office hours: Thu 16:30-17:30, Sun 16:30-18:30, or by appointment
Ranganath Kondapally | Sudikoff 112 | 6-0569 | Office hours: Thu 16:30-17:30, Sun 16:30-18:30, 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

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	Sep 26	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
Week 1	2	Sep 28	0.1, 0.2, 0.3	—	Types of proof: by construction, by contradiction, by induction (slides)

Week 2	3	Oct 1	0.4	—	Strings and languages; Finite automata introduced (slides)
	4	Oct 2 (X-hr)	1.1 up to p34	—	More on (deterministic) finite automata; some examples of DFAs
	5	Oct 3	1.1	—	Formal definition of DFA as (Q,Σ,δ,q₀,F); further examples; the third-last-char challenge
	6	Oct 5	—	—	NFA introduced; Examples; Formalization of NFAs and DFA/NFA computation

Week 3	7	Oct 8	—	HW1	More on NFAs; The union, concatenation and Kleene star operations
	8	Oct 9 (X-hr)	—	—	Regular expressions, examples, conversion to NFA (lecture notes)
	9	Oct 10	1.3 up to p66	—	Equivalence of DFAs, NFAs and regular expressions, I
	10	Oct 12	1.2	—	Equivalence of DFAs, NFAs and regular expressions, II (lecture notes)

Week 4	11	Oct 15	1.3	HW2	The pumping lemma and its proof
	12	Oct 16 (X-hr)	1.4	—	Applications of the pumping lemma: proving languages to be non-regular
	13	Oct 17	—	—	Closure properties of regular languages
		Oct 19	No lecture; homecoming

Week 5	14	Oct 22	Chapter 1	HW3	Pushdown automata (PDAs); Examples
		Oct 23 (X-hr)	—	—	Quiz 1: closed-notes, in-class
	15	Oct 24	—	—	More examples of PDAs
	16	Oct 26	—	—	More examples of PDAs; Introduction to Context-Free Grammars

Week 6	17	Oct 29	2.2	HW4	Examples of CFGs; CFG for equally many 0s as 1s (lecture notes)
	18	Oct 30 (X-hr)	—	—	CFGs formalized; closure of CFLs under union, concatenation and Kleene star
	19	Oct 31	2.1	—	Equivalence of CFGs and PDAs, I: PDA to CFG
	20	Nov 2	—	—	Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)

Week 7	21	Nov 5	2.2 (again)	Midterm	Pumping lemma for context-free languages; Applications
	22	Nov 6 (X-hr)	2.3	—	Chomsky Normal Form; Proof of the pumping lemma for CFLs
	23	Nov 7	Chapter 2	—	Turing machines; Informal description and simple examples
	24	Nov 9	3.1	—	Two TM applets; formal definition of a TM

Week 8	25	Nov 12	—	HW5	Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
	26	Nov 13 (X-hr)	3.2 up to p150	—	Review session with TAs
	27	Nov 14	—	—	Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)
	28	Nov 16	Chapter 3	—	Enumerator TMs; Decision problems for the major language classes: A_DFA, A_CFG and A_TM

Week 9	29	Nov 19	—	HW6	Decidability of A_DFA, A_CFG; Recognizability of A_TM; Undecidability of A_TM; Unrecognizability of A_TM
Week 9		Nov 20 (X-hr)	4.1	—	Quiz 2: closed-notes, in-class

Week 10	30	Nov 26	4.1 (again)	—	Reductions; Decidability of E_DFA, ALL_DFA, EQ_DFA, E_CFG; Unrecognizability of E_TM
	31	Nov 27 (X-hr)	Chapter 4	—	Time complexity, P and NP
	32	Nov 28	5.1 up to p192; 5.3	HW7	NP-completeness and polynomial time reductions (slides)
	33	Nov 30	7.1 – 7.3	—	More NP-completeness proofs

Week 11	34	Dec 3	7.4 up to p276; 7.5	—	Computation tableaux; The Cook-Levin theorem
Week 11	35	Dec 4 (X-hr)	7.5	HW8 (optional)	Unrecognizability of ALL_CFG; Wrap up

		Dec 10	Take-home 48-hour final exam, due at 6:00pm sharp Please the click the above link for info on the final exam. Your clock won't start until you fill out your password on that page.

Solutions to Homework and Exam Problems

Grades Database

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