| Instructor: |
Tim Wylie EIEAB 3.219 956-665-2577 timothy.wylie@utrgv.edu |
| CRN: | 37785 |
| Book: | Introduction to the Theory of Computation. M. Sipser, 3rd edition, 2012. |
| Syllabus: | CSCI4325_syllabus.pdf |
| Schedule: | Lecture: TR, 9:30 a.m. - 10:45 a.m., ELABN 117 |
| Final: | Dec. 18th (R), 8:00 a.m. - 9:45 a.m., ELABN 117 |
| Week | T | R |
| 9/2 - 9/4 | Introduction/Overview | Discrete review |
| 9/9 - 9/11 | DFAs/Regular Languages | |
| 9/16 - 9/18 | NFAs | NFAs/Regex |
| 9/23 - 9/25 | DFA/NFA equivalence | Regex equivalence |
| 9/30 - 10/2 | Review | Exam 1 |
| 10/7 - 10/9 | Pumping Lemma | TMs/TM variants |
| 10/14 - 10/16 | Nondet. TMs | Church/Turing |
| 10/21 - 10/23 | Decidability | |
| 10/28 - 10/30 | Decidability | Countable/Uncountable |
| 11/4 - 11/6 | Undecidability/Reductions | LBAs/review |
| 11/11 - 11/13 | Exam 2 | Asymptotic analysis |
| 11/18 - 11/20 | P, computational models | NP, verifiers |
| 11/25 - 11/27 | Reductions | Thanksgiving |
| 12/2 - 12/4 | Reductions | QBF/Hierarchy |
| 12/9 - 12/11 | Log Space | Misc. |
| 12/16 - 12/18 | No class | Final |
| Due Date | Review |
| 1 | review1.pdf |
| 2 | review2.pdf |
| 3 | review3.pdf |
| 4 | review4.pdf |
| Post Date | Paper | Comments |
| 1 | Logicomix | A fun graphic novel about Bertrand Russell and first-order logic |
| 2 | The Thrilling Adventures of Lovelace and Babbage | A (mostly fictional) graphic novel about Ada Byron (Lady of Lovelace) and Charles Babbage. Several parts of this book are on the website as well for free. |
| 3 | Computer solution to the 17-point Erdos-Szekeres problem | |
| 4 | Combinatorial Optimization Problems in Self-Assembly | A good introduction to the model and basic problems |
| 5 | Hardness Results on Curve/Point Set Matching with Fréchet Distance | Interesting Reduction |
| 6 | Classic Nintendo Games are (Computationally) Hard | Fun reductions |
| 7 | The Computational Complexity of Portal and Other 3D Video Games | |
| 8 | Staged One-Dimensional Staged Self-assembly | CFGs, yay! |
| 9 | A Simple Proof for the NP-Hardness of Edge Labeling | One of the best explanations for planar 3SAT reductions. |