| Instructor: |
Tim Wylie EIEAB 3.219 956-665-2577 timothy.wylie@utrgv.edu |
| CRN: | S01: 60754, S03: 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., EIEAB 2.205 |
| Final S01: | May 12th (M), 1:15 p.m. - 3:00 p.m., EIEAB 2.205 |
| Schedule S03: | Lecture: MW, 3:30 p.m. - 4:45 p.m., EIEAB 1.212 |
| Final S03: | May 14th (W), 1:15 p.m. - 3:00 p.m., EIEAB 1.212 |
| Week | T | R |
| 1/20 - 1/22 | No class | Introduction/Overview |
| 1/27 - 1/29 | Discrete review | DFAs/Regular Languages |
| 2/3 - 2/5 | NFAs | NFAs/Regex |
| 2/10 - 2/12 | Regex | Regex equivalence |
| 2/17 - 2/19 | Non-regular languages | CFGs |
| 2/24 - 2/26 | CFGs | Exam 1 |
| 3/3 - 3/5 | TMs | TM Variants |
| 3/10 - 3/12 | TM Variants | Church-Turing Thesis |
| 3/17 - 3/19 | Spring Break | Spring Break |
| 3/24 - 3/26 | Decidability | Undecidability |
| 3/31 - 4/2 | Reductions | Reductions/Review |
| 4/7 - 4/9 | Exam 2 | Complexity |
| 4/14 - 4/16 | ||
| 4/21 - 4/23 | Reductions | QBF/Hierarchy |
| 4/28 - 4/30 | Log Space | Misc. |
| 5/5 - 5/7 | No class | Final |
| 5/12 - 5/14 | S1 Final | S3 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. |