CS 39 (Fall 2005): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2005

[ 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 30] The final exam has been posted and is due at 6:00pm sharp on Dec 6. Please note that THERE IS NO "LATE PENALTY" PROVISION for the final exam. If you haven't turned in the exam by the deadline, you score zero for the entire exam.
[Nov 9] URL for the two Turing Machine applets we saw in class are here and here. Please play with them sometime.
[Nov 4] Solutions to the midterm have been posted. Please note that all posted solutions are part of the required reading for the course.
[Oct 4] Homeworks are due each Wednesday at 12:30 (i.e. before class). Please submit them into Prof. Chakrabarti's mailbox. Note the late homework policy.
[Sep 28] A note about asking questions about homeworks via blitz. If you send your question to the instructor, please also send a copy to the TA, so as to get a quicker response. Plus, the TA needs to be kept in the loop, because he is doing the grading.
[Sep 15] 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: MF 10:00-11:30 or by appointment

Teaching Assistant

Khanh Do Ba | Sudikoff 114 | 6-5573 | Office hours: Tu 17:00-19:00, Th 19:00-21: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.

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