Theory of Computation
Instructor: Don SheehyEmail: donald@engr.uconn.edu
Office: ITEB 361
Office Hours: Mon 2:00-3:00pm. Th 2:00-3:00pm.
Grader: Ozgur Oksuz (ozgur.oksuz at engr.uconn.edu)
Office: ITEB 140
Office Hours: Mon 11:00-12:00pm. Tu 11:00-12:00pm.
Schedule
| Date | Topic | Reading | Homework Out | Homework Due |
| 1/21/2014 | Automata, Computability, and Complexity | 0.1-0.2 | HW 1 | |
| 1/23/2014 | Definitions, Theorems, and Proofs | 0.3-0.4 | ||
| 1/28/2014 | Finite Automata | 1.1 | HW 2 | 1 |
| 1/30/2014 | Nondeterminism | 1.2 | ||
| 2/4/2014 | Regular Expressions | 1.3 | 2 | |
| 2/11/2014 | More Regular Expressions | 1.3 | HW 3 | |
| 2/18/2014 |
Nonregular Languages
|
1.4 | 3 | |
| 2/20/2014 | Context-Free Grammars I | 2.1 | ||
| 2/25/2014 | Midterm | |||
| 2/27/2014 | Context-Free Grammars II | 2.1 | ||
| 3/4/2014 | Equivalence of PDAs and CFG I | 2.2 | HW 4 | |
| 3/6/2014 | Equivalence of PDAs and CFG II | 2.2 | ||
| 3/11/2014 |
Non-Context-free Languages
|
2.3 | HW 5 | 4 |
| 3/13/2014 | Turing Machines | 3.1 | ||
| 3/16-23/2014 | Spring Break | |||
| 3/25/2014 | Turing Machine Variants | 3.2 | ||
| 3/27/2014 | Turing Machine Variants | 3.2 | 5 | |
| 4/1/2014 | Decidability | 4.1 | HW 6 | |
| 4/3/2014 | Undecidability | 4.2 | ||
| 4/8/2014 | Measuring Complexity | 7.1 | HW 7 | 6 |
| 4/10/2014 | The Class P | 7.2 | ||
| 4/15/2014 | The Class NP | 7.3 | ||
| 4/17/2014 | NP-Completeness | 7.4 | HW 8 | |
| 4/22/2014 | NP-Completeness | 7.4, 7.5 | HW 9 | |
| 4/24/2014 | Proving Problems are NP-Complete | 7.5 | ||
| 4/29/2014 | Course Review | 9 | ||
| 5/1/2014 | Final Exam |