| Instructor: |
Tim Wylie EIEAB 3.219 956-665-2577 timothy.wylie@utrgv.edu |
| CRN: | 12772 |
| Book: | Introduction to the Theory of Computation. M. Sipser, 3rd edition, 2012. |
| Syllabus: | Syllabus, UTRGV_Syllabus |
| Schedule S01: | Lecture: TR, 12:30 p.m. - 1:45 p.m., EIEAB 1.212 |
| Final S01: | Dec. 10th (R), 10:15 a.m. - 12:00 p.m., EIEAB 1.212 |
| Week | M | W |
| 8/25 - 8/27 | No class | Introduction/Overview |
| 9/1 - 9/3 | Discrete review/DFAs | DFAs/Regular Languages (Quiz 1) |
| 9/8 - 9/10 | NFAs | NFAs/Regex (Exam 1) |
| 9/15 - 9/17 | DFA/NFA equivalence | Regex equivalence (Quiz 2) |
| 9/22 - 9/24 | (Exam 2) | |
| 9/29 - 10/1 | Pumping Lemma | TMs/TM variants (Quiz 3) |
| 10/6 - 10/8 | Nondet. TMs, Church/Turing | Decidability (Exam 3) |
| 10/13 - 10/15 | Decidability | Countable/Uncountable (Quiz 4) |
| 10/20 - 10/22 | Spring Break | Spring Break |
| 10/27 - 10/29 | Undecidability/Reductions | LBAs/review (Exam 4) |
| 11/3 - 11/5 | Asymptotic analysis | P, computational models (Quiz 5) |
| 11/10 - 11/12 | P, computational models | NP, verifiers (Exam 5) |
| 11/17 - 11/19 | Hardness intro | Reductions (Quiz 6) |
| 11/24 - 11/26 | Reductions (Exam 6) | No class |
| 12/1 - 12/3 | Space complexity | QBF (Quiz 7) |
| 12/8 - 12/10 | No class | FPT/Approximations (Exam 7) |
| Quiz/Exam | Review |
| 1 | practice1.pdf |
| 2 | practice2.pdf |
| 3 | practice3.pdf |
| 4 | practice4.pdf |
| 5 | practice5.pdf |
| 6 | practice6.pdf |
| 7 | practice7.pdf |