CS 39 (Fall 2006): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2006

[ 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 29] Here is the Final Exam. Please read the instructions carefully before you begin. Good luck to all!
[Nov 15] Solutions to Quiz 2 have been posted. Please read.
[Nov 8] The late submission policy has been clarified with two additional paragraphs added. Please read these.
[Nov 7] URL for the two Turing Machine applets we saw in class are here and here. Play with them sometime. They'll enhance your understanding.
[Oct 31] Some notes for Lecture 21 have been posted below. These cover a proof that is not written out in full in the textbook.
[Oct 27] Solutions to all homeworks and quizzes so far have been posted. You are allowed (in fact, encouraged) to consult these as you work on your midterm.
[Oct 19] Challenge Problem CP1 is officially retired as of today, i.e., you can no longer get credit for it.
[Oct 17] Solutions to Quiz 1 have been posted. Please read these and concentrate on the ones where you lost points. This is important preparation for the rest of the course.
[Oct 16] Graded homeworks can be picked up from the box atop the one where you submit your homeworks.
[Oct 16] Solutions to HW2 have been posted.
[Oct 4] Instructions for submitting homeworks: please submit these in the box marked "CS39 HW in" near the main entrance to Sudikoff. Homeworks must be submitted by 12:30 on the day they are due (i.e., before class).
[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 | MWF 12:30-13:35, X-hr T 13:00-13:50

Instructor

Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Mon & Fri 10:00-11:30 or by appointment

Teaching Assistants

Vibhor Bhatt | Sudikoff 221 | 6-8753 | Office hours: Tue 15:00-17:00, Sun 18:00-19:00 or by appointment
Hong Lu | Sudikoff 062 | 6-???? | Office hours: Mon 19:00-21:00, Sun 19:00-20: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

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.

L#	Date	Reading Due	Homework Due	Class Topic
1	Sep 20	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
2	Sep 22	0.1, 0.2, 0.3	—	Types of proof: by construction, by contradiction, by induction (slides)
3	Sep 25	0.4	—	Strings and languages; Finite automata introduced (slides)
4	Sep 26 (X-hr)	1.1 up to p34	—	More on (deterministic) finite automata; examples of DFAs; third-last-char challenge
5	Sep 27	1.1	—	Formal definition of DFA as (Q,Σ,δ,q₀,F); DFA computation formalized
6	Sep 29	—	—	NFA introduced; Examples; Formalization of NFAs and NFA computation
7	Oct 2	—	—	Designing NFAs; Union and concatenation of two regular languages is regular
8	Oct 3 (X-hr)	—	—	Kleene star; Regular expressions and examples
9	Oct 4	1.3 up to p66	HW1	Equivalence of DFAs, NFAs and regular expressions, I
10	Oct 6	1.2	—	Equivalence of DFAs, NFAs and regular expressions, II
11	Oct 9	1.3	—	Equivalence of DFAs, NFAs and regular expressions, III (lecture notes)
12	Oct 10 (X-hr)	—	—	Example of DFA to RegExp conversion; The pumping lemma
13	Oct 11	—	HW2	Proof and applications of the pumping lemma
	Oct 13	No lecture; homecoming
14	Oct 16	Chapter 1	—	Closure properties of regular languages
	Oct 17 (X-hr)	—	—	Quiz 1: closed-notes, in-class
15	Oct 18	—	HW3	Pushdown automata (PDAs); Examples
	Oct 20	—	—	More examples of PDAs and a formal definition
16	Oct 23	2.2	—	Closure of context-free languages under union, concatenation and Kleene star (Vibhor)
17	Oct 24 (X-hr)	—	—	Closure and non-closure properties; a PDA for not-ww (Vibhor)
18	Oct 25	—	HW4	Context-free grammars; Simple examples
19	Oct 27	—	—	CFGs formalized; a CFG for equally many 0s and 1s (lecture notes)
20	Oct 30	2.1	—	Equivalence of CFGs and PDAs, I: PDA to CFG
21	Oct 31 (X-hr)	—	—	Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
22	Nov 1	2.2 (again)	Midterm	Pumping lemma for context-free languages; Applications
23	Nov 3	2.3	—	Chomsky Normal Form; Proof of the pumping lemma for CFLs
24	Nov 6	Chapter 2	—	Turing machines; Informal description and simple examples
25	Nov 7 (X-hr)	3.1	—	Two TM applets; formal definition of a TM
26	Nov 8	—	HW5	Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
27	Nov 10	3.2 up to p138	—	Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)
28	Nov 13	Chapter 3	—	Enumerator TMs; Decision problems for the major language classes: A_DFA, A_CFG and A_TM
	Nov 14 (X-hr)	—	—	Quiz 2: closed-notes, in-class
29	Nov 15	4.1	HW6	Decidability of A_DFA, A_CFG; Recognizability of A_TM; Undecidability of A_TM and the halting problem
30	Nov 17	4.2 up to p180	—	Decidability of E_DFA, ALL_DFA, EQ_DFA, E_CFG; Unrecognizability of A_TM and E_TM
31	Nov 20	Chapter 4; 5.1 up to p192; 5.3	—	Time complexity, P and NP
32	Nov 21 (X-hr)	7.1 – 7.3	—	NP-completeness and polynomial time reductions (slides)
33	Nov 27	7.4 up to p276; 7.5	HW7	More NP-completeness proofs
34	Nov 28 (X-hr)	7.5	—	Computation tableaux; The Cook-Levin theorem; Unrecognizability of ALL_CFG;
33	Nov 29	7.4	HW8 (optional)	Wrap up
	Dec 5	Take-home 48-hour final exam, due at 6:00pm sharp

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.