This page is subject to update through the term. It was last modified on Apr 13, 2012.
Time: TTh 2:00-3:15pm
Place: 300 Main St., B112
Syllabus
Textbooks:
| Date |
Topics |
Slides |
| 01/10/12 |
Mathematical background I:
sets and sequences, functions and relations, graphs (Ch.
0.1-0.2) |
Lecture 1 |
| 01/12/12 |
Mathematical background II:
languages, proof techniques (Ch. 0.2-0.4) |
Lecture 2 |
| 01/17/12 |
DFA, State diagrams, Regular
languages (Ch. 1.1) |
Lecture 3 |
| 01/19/12 |
NFA, Equivalence of DFAs and
NFAs (Ch. 1.2) |
Lecture 4 |
| 01/24/12 |
Regular Expressions, Equivalence of GNFAs and NFAs (Ch. 1.3) | Lecture 5 |
| 01/26/12 |
Nonregular Languages, Pumping Lemma (Ch. 1.4) | Lecture 6 |
| 01/31/12 |
Practical session |
n/a |
| 02/02/12 |
Context-free grammars, Parse
Trees, Ambiguity, Chomsky normal form (Ch. 2.1) |
Lecture 7 |
| 02/07/12 |
Pushdown Automata, Equivalence of PDAs and CFGs (Ch. 2.2) | Lecture 8 |
| 02/09/12 |
Pumping Lemma for CFL, Non-context-free languages (Ch. 2.3) | Lecture 9 |
| 02/14/12 |
Turing Machines, Deciders and Recognizers, Variants of Turing Machines (Ch. 3.1-3.2) | Lecture
10 |
| 02/16/12 |
Algorithms, Church-Turing thesis (Ch. 3.3). Review session of part I. | Lecture
11 |
| 02/21/12 |
Midterm 1 |
n/a |
| 02/23/12 |
Decidable Languages (Ch. 4.1). Review of Midterm 1. | Lecture
12 |
| 02/28/12 |
Halting Problem, Undecidable Languages (Ch. 4.2) | Lecture
13 |
| 03/01/12 |
Reducibility (Ch. 5.1) | Lecture
14 |
| 03/13/12 |
Reducibility via Computation
Histories (Ch. 5.1) |
Lecture
15 |
| 03/15/12 |
Post Correspondence Problem
(Ch. 5.2) |
Lecture
16 |
| 03/20/12 |
Computable Functions, Mapping Reducibility (Ch. 5.3) | Lecture
17 |
| 03/22/12 |
Time Complexity (Ch. 7.1) | Lecture
18 |
| 03/27/12 |
Review session |
n/a |
| 03/29/12 |
Midterm 2 |
n/a |
| 04/03/12 |
The class P (Ch. 7.2) (see also slides 13-24 on Dynamic Programming) | Lecture
19 |
| 04/05/12 |
The class NP (Ch. 7.3) |
Lecture
20 |
| 04/10/12 |
NO CLASS |
n/a |
| 04/12/12 |
NP-completeness, Polynomial Time Reducibility | Lecture 21 |
| 04/13/12 |
Review of Midterm 2 |
n/a |
| 04/17/12 |
NO CLASS |
n/a |
| 04/19/12 |
Review of Homework 3 and Part III | n/a |
| 05/02/12 |
Final Exam |
n/a |
Graduate students do homeworks for full credit, but undergrads
may do them as well for extra credit. It is encouraged that
textual part of solutions is typed and printed rather than
handwritten.