[ 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
- [May 28] The final exam is now available from this
webpage. Please see the bottom of the schedule table.
- [Apr 16] The midterm exam is now available from this
webpage. Please scroll down to the schedule table.
- [Mar 24] Please send email to the professor (Amit Chakrabarti)
with your name (only first and last name, no initials)
and a password for accessing your grades in our 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 | 11 hour | Mon-Wed-Fri 11:15-12:20, X-hr Tue 12:00-12:50
|
Instructor
|
Amit Chakrabarti
Sudikoff 107 | 646-1710 |
Office hours: Mon 17:00-18:00, Fri 15:00-16:00, or by appointment
|
Teaching Assistant
|
Zheyu Liu
Sudikoff 114 | 603-277-0971 |
Office hours: Sun 15:00-16:00, Mon 13:00-14:00, or by appointment
|
Textbook
|
Required:
"Introduction to the Theory of Computation," Third Edition.
Michael Sipser.
Suggested additional reading (not required):
"Introduction to Automata Theory, Languages and Computation."
J. E. Hopcroft and J. D. Ullman.
|
Prerequisites
|
Either CS 30 or CS 31, 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
TBA
Please be sure to read and understand the Homework Grading Guidelines and the
Late Submission Policy.
Lecture Number
and Date |
Reading Due
Before Class |
Homework
Due |
Topics Covered in
This Lecture |
| |
Week
1 |
1 |
Mar 24 |
— |
— |
Welcome, administrivia, overview; Mathematical notation
(slides) |
|
| 2 |
Mar 25 (X-hr) |
0.1, 0.2, 0.3 |
— |
Types of proof (direct, contradiction, induction); Strings and languages
(slides) |
| 3 |
Mar 26 |
0.4 |
— |
Finite automata; Basic DFA examples
|
| 4 |
Mar 28 |
1.1 up to p34 |
— |
DFA formalized as (Q,Σ,δ,q0,F);
Formalization of DFA computations;
NFAs; Examples
|
| |
Week
2 |
5 |
Mar 31 |
1.1 |
— |
Formalization of NFAs and their computation;
NFA for L1∪L2
|
| 6 |
Apr 1 (X-hr) |
1.2 |
— |
|
| 7 |
Apr 2 |
— |
HW1 |
Kleene's Theorem I: Conversion of NFA to DFA
|
| 8 |
Apr 4 |
1.3 up to p69 |
— |
Kleene's Theorem II: Conversion of DFA to regular expression
( lecture notes)
|
| |
Week
3 |
9 |
Apr 7 |
— |
— |
The pumping lemma and proofs of non-regularity |
| 10 |
Apr 8 (X-hr) |
1.3 |
— |
Closure properties of regular languages |
| 11 |
Apr 9 |
1.4 |
HW2 |
Pushdown automata; Examples of PDAs |
| |
Apr 11 |
Chapter 1 |
— |
Quiz 1: closed-notes, in-class |
| |
Week
4 |
12 |
Apr 14 |
— |
— |
Formal definition of a PDA; More examples; Closure under ∪, ∘, *
|
| 13 |
Apr 15 (X-hr) |
2.2 up to p116 |
— |
Context-Free Grammars (CFGs); Basic examples |
| 14 |
Apr 16 |
— |
HW3 |
Formal definition of a CFG; Ambiguity; CFG for N 0 = N 1
( lecture notes)
|
| 15 |
Apr 18 |
2.1 up to p108 |
— |
|
| |
Week
5 |
16 |
Apr 21 |
2.1 |
— |
Equivalence of CFGs and PDAs, I: PDA to CFG
|
| 17 |
Apr 22 (X-hr) |
— |
— |
|
| 18 |
Apr 23 |
2.2 |
Midterm |
Pumping lemma for CFLs; Applications; Use of closure properties |
| 19 |
Apr 25 |
2.3 |
— |
Proof of the CFL pumping lemma; CFL wrap-up; Turing machines
( palindromes,
adder)
|
| |
Week
6 |
20 |
Apr 28 |
3.1 |
— |
Formal description of TMs; Deciders/recognizers;
Implementation Descriptions
|
| 21 |
Apr 29 (X-hr) |
— |
— |
Multi-tape TMs; Equivalence with single-tape TMs
( slides)
|
| 22 |
Apr 30 |
— |
HW4 |
Nondeterministic TMs;
The RAM model; Church-Turing Thesis
( slides)
|
| 23 |
May 2 |
3.1 |
— |
Decision problems for the major language classes:
ADFA, ACFG and ATM
|
| |
Week
7 |
24 |
May 5 |
3.2 up to p150 |
— |
Decidability of ADFA, ACFG;
(Mapping) reductions;
Recognizability of ATM; Undecidability of ATM
|
| 25 |
May 6 (X-hr) |
Chapter 3 |
— |
Decidability of EDFA, ALLDFA, EQDFA;
Decidability of ECFG;
Unrecognizability of
ATM
|
| 26 |
May 7 |
4.1 |
HW5 |
Further reductions;
Unrecognizability of ETM, EQTM;
Discussion of ALLTM, INTTM
|
| |
May 9 |
Chapter 4 |
— |
Quiz 2: closed-notes, in-class |
| |
Week
8 |
27 |
May 12 |
5.1 up to p192; 5.3 |
— |
Time complexity, P and NP |
| 28 |
May 13 (X-hr) |
— |
— |
NP-completeness and polynomial time reductions
( slides) |
| 29 |
May 14 |
7.1 |
HW6 |
More NP-completeness proofs: IND-SET, CLIQUE, UHAMCYCLE |
| 30 |
May 16 |
7.1 – 7.3 |
— |
Yet more NP-completeness: TSP, 3-COL |
| |
Week
9 |
31 |
May 19 |
TBD |
— |
Tractability of 2-COL, 2-SAT; Computational tableaux
|
| 32 |
May 20 (X-hr) |
TBD |
— |
Undecidability of INTCFG
|
| 33 |
May 21 |
— |
HW7 |
Unrecognizability of ALLCFG;
The Cook-Levin Theorem |
| 34 |
May 23 |
— |
— |
Space complexity; Savitch's Theorem |
| |
Week
10 |
|
May 26 |
TBD |
— |
No class: Memorial Day |
| 35 |
May 27 (X-hr) |
TBD |
HW8 (optional) |
Not used |
| 36 |
May 28 |
TBD |
— |
Review of unresolved homework/exam questions; Wrap-up |
| |
| Deadline Jun 3 |
Take-home 48-hour
final exam, due at 5:00pm sharp
|
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.
