| Instructor: |
Tim Wylie EIEAB 3.219 956-665-2577 timothy.wylie@utrgv.edu |
| CRN: | S01: 66646 |
| Book: | Introduction to the Theory of Computation. M. Sipser, 3rd edition, 2012. |
| Syllabus: | CSCI4325_syllabus.pdf |
| Schedule: | Lecture: M-F, 9:45 a.m. - 11:15 a.m., EMAGC 1.202 |
| Final S01: | July 15th (T), 10:00 a.m. - 11:45 a.m., EMAGC 1.202 |
| Week | Day | Topic |
|---|---|---|
| 1 | M - 6/9 | Introduction/Overview |
| T - 6/10 | Discrete review | |
| W - 6/11 | DFAs/Regular Languages | |
| R - 6/12 | NFAs | |
| F - 6/13 | NFAs/Regex | |
| 2 | M - 6/16 | DFA/NFA equivalence |
| T - 6/17 | Regex equivalence | |
| W - 6/18 | Review | |
| R - 6/19 | Exam 1 | |
| F - 6/20 | TMs | |
| 3 | M - 6/23 | TM variants |
| T - 6/24 | Nondet. TMs | |
| W - 6/25 | Decidability | |
| R - 6/26 | Countable/Uncountable | |
| F - 6/27 | Undecidability | |
| 4 | M - 6/30 | Undecidable reductions |
| T - 7/1 | LBAs/review | |
| W - 7/2 | Exam 2 | |
| R - 7/3 | P, computational models | |
| F - 7/4 | NP, verifiers | |
| 5 | M - 7/7 | NP-hardness reductions |
| T - 7/8 | QBF/Hierarchy | |
| W - 7/9 | Log Space | |
| R - 7/10 | ||
| F - 7/11 | Approximations/FPT | |
| 5 | M - 7/14 | Review |
| T - 7/15 | 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. |