Topics	Slides per page
Introduction	1(pdf) 2(pdf)
Finite Automata	1(pdf) 2(pdf)
Finite Automata (cont.)	1(pdf) 2(pdf)
Application of FA's (by --)
Regular Languages	1(pdf) 2(pdf)
Non-Regular Languages	1(pdf) 2(pdf)
Application of Regular Expressions (by --)
Context-Free Grammars	1(pdf) 2(pdf)
Pushdown Automata	1(pdf) 2(pdf)
Non-Context-Free Languages	1(pdf) 2(pdf)
Application of Context-Free Grammars (by --)
Turing Machines	1(pdf) 2(pdf)
Variants of Turing Machine	1(pdf) 2(pdf)
PDA with the ability to flip its stacks (by --)	(paper)
Markup Languages & XML (by --)
Algorithms and Turing Machines	1(pdf) 2(pdf)
Decidable Languages	1(pdf) 2(pdf)
Turing Machines and Computers (by --)
Undecidable Languages	1(pdf) 2(pdf)
Reducibility	1(pdf) 2(pdf)
Post's Correspondence Problem is Undecidable (by --)
Time Complexity	1(pdf) 2(pdf)
Complexity Classes P and NP	1(pdf) 2(pdf)
NP-completeness	1(pdf) 2(pdf)
NP-complete Problems	1(pdf) 2(pdf)

Office hours: MW 1:45 - 3:45 PM or by appointment

Textbook:

Michael Sipser,

Introduction to the Theory of Computation (2^nd edition),

Thomson, 2006

HOMEWORKS

Homework #1: Problems 0.1 (p. 25); 0.3, 0.7, 0.8 (p. 26); 0.9, 0.10, 0.11 (p. 27). (Due 01/29/2018)
Homework #2: Problems 1.3, 1.4(a,e) (p.83); 1.5(c,d), 1.6(b,c), 1.7(b), 1.8(a) (p.84); 1.9(a), 1.10(a) (p.85); 1.16(a) (p.86). (Due 02/12/2018)
Homework #3: Problem 1.17, 1.18, 1.19(a), 1.20(a,e), 1.21(b), 1.29(b), 1.30 (Due 02/19/2018)
Homework #4: Problem 2.4(b,c), 2.5 (for 2.4(b,c)), 2.11, 2.13(a), 2.14 (Due 02/26/2018)
Homework #5: Problem 3.1(c,d), 3.2(b,d) (p.159), 3.7, 3.8(c) (p.160), 3.15 (b,e) (p.161) (Due 04/02/2018)
Homework #6: Problem 4.2, 4.3, 4.5 (c,f), 4.6 (p. 183), 5.9 (p. 211). (Due 04/16/2018)
Homework #7: Problem 7.5, 7.6 (p. 294), 7.7, 7.9 (p. 295), 7.20 (p. 296). (Due 04/25/2018; put in my mailbox in Room MSB 239 by 5 pm)

ExtraCredit problem is due March 19 (see slide 9 in Variants of Turing Machine).

EXAMS

Monday, March 12, 2018, 05:30 - 06:45 p.m. (all material covered before Turing Machines) info
Monday, May 7, 2018, 05:45 - 08:00 p.m. (all material covered starting from Turing Machines) info