CS 39 (Fall 2004): Amit Chakrabarti

Teaching Home

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2004

[ 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.

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 is ready! Click here to access the exam. There are general instructions on page 1 which you may look at before you are ready to start. But once you look at page 2, your time has started and you must turn in the exam within 48 hours. Please turn in the exam into Chakrabarti's mailbox and not Huang's.
[Nov 22] For those who stuck around after today's class to muse about programs that print themselves out, here is an excellent writeup about such programs and how they work.
[Nov 12] The two Turing Machine applets shown in class on Nov 9 are here and here.
[Oct 24] Some explanations and examples have been added to HW4 that should answer some basic questions you may have about equivalence classes.
[Oct 5] The administrative details page has a new section titled "challenge problems" which talks about certain extra credit problems that will show up on the homeworks from time to time. Please read that section carefully.
[Oct 1] The slides used for the first three lectures are now up on the website; see the schedule table.
[Sep 28] Homeowrk 1 is ready and is due on Oct 6 at the start of class. To get to the homework, click the link in the schedule table. If you are unable to view or print the homework, let the instructor know right away. Please review the guidelines for homeworks on the administrative details page.
[Sep 22] 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 115 | 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

Chien-Chung Huang | Sudikoff 221 | 6-8753 | Office hours: TTh 16:15-18:15

Textbook

Required:
"Introduction to the Theory of Computation." 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.

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.

For now, the dates in the table below are totally inaccurate, as should be obvious.

Date	Reading Due	Homework Due	Class Topic
Sep 22	—	—	Welcome, administrivia, overview; Mathematical notation (slides)
Sep 24	0.1, 0.2, 0.3	—	Types of proof: by construction, by contradiction, by induction (slides)
Sep 27	0.4	—	Strings and languages; Finite automata introduced (slides)
Sep 28 (X-hr)	1.1 up to p34	—	More on (deterministic) finite automata; Understanding the behavior of specific DFAs
Sep 29	1.1	—	Designing DFAs; Formal definition of a DFA
Oct 1	—	—	Formal definition of DFA recap; DFA computation formalized; NFA introduced
Oct 4	—	—	Designing NFAs; Union of two regular languages is regular
Oct 5 (X-hr)	—	—	The concatenation of two regular languages is regular; Kleene star defined
Oct 6	—	HW1	Regular expressions; Equivalence of DFAs, NFAs and regular expressions, I
Oct 8	1.2	—	Equivalence of DFAs, NFAs and regular expressions, II
Oct 11	1.3	—	Equivalence of DFAs, NFAs and regular expressions, III (lecture notes)
Oct 12 (X-hr)	—	—	Example of DFA to RegExp conversion; The pumping lemma
Oct 13	—	HW2	Applications of the pumping lemma; Closure properties of regular languages
Oct 15	1.4	—	Problem solving session, led by Chien-Chung Huang
Oct 18	Chapter 1	—	Quiz 1: closed-notes, in-class
Oct 19 (X-hr)	No lecture today
Oct 20	—	HW3	Pushdown automata (guest lecture by Srdjan Petrovic)
Oct 22	2.2	—	More examples of PDAs; Closure (or not) properties
Oct 25	2.2 (reread)	—	Closure and non-closure properties continued; PDA for not-ww
Oct 26 (X-hr)	—	—	Context-free grammars; Examples
Oct 27	—	HW4	Equivalence of CFGs and PDAs, I (CFG to PDA, informal)
Oct 29	—	—	Equivalence of CFGs and PDAs, II (CFG to PDA, formal; PDA to CFG, idea)
Nov 1	2.1	—	Equivalence of CFGs and PDAs, III (PDA to CFG, almost formal)
Nov 2 (X-hr)	No lecture today
Nov 3	—	Midterm	Chomsky normal form; Pumping lemma for context-free languages
Nov 5	2.3	—	Proof and applications of the pumping lemma for CFLs
Nov 8	Chapter 2	—	Turing machines; Informal description and simple examples
Nov 9 (X-hr)	3.1 up to p133	—	Formal definition of TMs; A TM solution for {0ⁿ1ⁿ2ⁿ: n ≥ 0}
Nov 10	—	HW5	Configurations, deciders/recognizers, multi-tape TMs (slides)
Nov 12	—	—	Closure properties of decidable languages; Nondeterministic TMs (slides)
Nov 15	—	—	Church-Turing Thesis; Enumerator TMs
Nov 16 (X-hr)	—	—	Quiz 2: closed-notes, in-class
Nov 17	Chapter 3	HW6	Decision problems for the major language classes: A_DFA, A_CFG and A_TM
Nov 19	4.1 (and 4.2 ?)	—	Undecidability of A_TM and the halting problem; E_DFA, E_CFG and E_TM; A_TM
Nov 22	4.2	—	Reduction from A_TM to E_TM; Undecidability of ALL_CFG
Nov 23 (X-hr)	—	HW7	More undecidable CFG problems; time complexity, P and NP
Nov 29	—	—	NP-completeness and polynomial time reductions (slides)
Nov 30 (X-hr)	7.5	—	The Cook-Levin theorem
Dec 1	7.4	HW8 (optional)	Wrap up
Dec 7	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.