Theory of Computation

Instructor: Don Sheehy
Email: 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