| Instructor: |
Tim Wylie EIEAB 3.219 956-665-2577 timothy.wylie@utrgv.edu |
| CRN: 60754/70395 | |
| Book: | Introduction to the Theory of Computation. M. Sipser, 3rd edition, 2012. |
| Syllabus: | CSCI4325_syllabus.pdf |
| Schedule S01: | Lecture: MW, 2:00 p.m. - 3:15 p.m., EENGR 1.272 |
| Final S01: | May 11th (M), 1:15 p.m. - 3:00 p.m., EENGR 1.272 |
| Schedule S03: | Lecture: MW, 3:30 p.m. - 4:45 p.m., EENGR 1.272 |
| Final S03: | May 13th (W), 1:15 p.m. - 3:00 p.m., EENGR 1.272 |
| Week | M | W |
| 1/19 - 1/21 | No class | Introduction/Overview |
| 1/26 - 1/28 | Discrete review | DFAs/Regular Languages (Quiz 1) |
| 2/2 - 2/4 | NFAs | NFAs/Regex (Exam 1) |
| 2/9 - 2/11 | DFA/NFA equivalence | Regex equivalence (Quiz 2) |
| 2/16 - 2/18 | (Exam 2) | |
| 2/23 - 2/25 | Pumping Lemma | TMs/TM variants (Quiz 3) |
| 3/2 - 3/4 | Nondet. TMs | Church/Turing (Exam 3) |
| 3/9 - 3/11 | Decidability | Countable/Uncountable (Quiz 4) |
| 3/16 - 3/18 | Spring Break | Spring Break |
| 3/23 - 3/25 | Undecidability/Reductions | LBAs/review (Exam 4) |
| 3/30 - 4/1 | Asymptotic analysis (Quiz 5) | |
| 4/6 - 4/8 | P, computational models | NP, verifiers (Exam 5) |
| 4/13 - 4/15 | Reductions | Thanksgiving (Quiz 6) |
| 4/20 - 4/22 | Reductions | QBF/Hierarchy (Exam 6) |
| 4/27 - 4/29 | Log Space | Misc. (Quiz 7) |
| 5/4 - 5/6 | (Exam 7) | |
| 5/11 - 5/13 | S01 Final | S03 Final |
| Quiz/Exam | Review |
| 1 | practice1.pdf |
| 2 | practice2.pdf |
| 3 | practice3.pdf |
| 4 | practice4.pdf |
| 5 | practice5.pdf |
| 6 | practice6.pdf |
| 7 | practice7.pdf |