Theory of Computation

Instructor: Don Sheehy
Email: donald@engr.uconn.edu
Office Hours: Mon 9:00-10:00am and Wed 9:00-10:00am in ITEB 361
Grader: Ozgur Oksuz (ozgur.oksuz at engr.uconn.edu)
Office: TBA, ITEB 140
Grader: Astha Patni

---

Schedule

1. Jan 21. Automata, Computability, and Complexity

   Reading: Sipser 0.1, 0.2

2. Jan 26. Definitions, Theorems, and Proofs

   Reading: Sipser 0.3, 0.4

3. Jan 28. Finite Automata

   Reading: Sipser 1.1

4. Feb 4. Nondeterminism

   Reading: Sipser 1.2

5. Feb 9. Regular Expressions

   Reading: Sipser 1.3

6. Feb 11. Regex's and intro to Nonregular Languages

   Reading: Sipser 1.3, 1.4

7. Feb 16. A Nonregular Languages

   Reading: See notes on HuskyCT

8. Feb 18. The Pumpling Lemma

   Reading: Sipser 1.4

9. Feb 23. Pushdown Automata (CFGs to PDAs)

   Reading: Sipser 2.2

10. Feb 25. Converting between Automata

    Reading: See notes on HuskyCT

11. Mar 4. Converting PDAs to CFGs

    Reading: Sipser 2.2

12. Mar 9. Midterm

    Reading: Sipser: Ch 0, Ch 1, 2.1 and 2.2

13. Mar 23. Turing Machines

    Reading: Sipser 3.1

14. Mar 25. Turing Machine Variants

    Reading: Sipser 3.2

15. Mar 30. A Definition of Algorithm

    Reading: Sipser 3.3

16. Apr 1. Decidable Languages

    Reading: Sipser 4.1

17. Apr 6. Undecidable Languages

    Reading: Sipser 4.2

18. Apr 8. Reductions and the Halting Problem

    Reading: Sipser 5.1

19. Apr 13. The Post Correspondence Problem

    Reading: Sipser 5.2

20. Apr 15. Measuring Time Complexity

    Reading: Sipser 7.1

21. Apr 20. The Class P

    Reading: Sipser 7.2

22. Apr 22. The Class NP

    Reading: Sipser 7.3

23. Apr 27. The Class NP-Complete

    Reading: Sipser 7.4

24. Apr 29. NP-Completeness and Reductions

    Reading: Sipser 7.5