Course Information

Instructor: Tim Wylie
EIEAB 3.219
956-665-2577
timothy.wylie@utrgv.edu
Teaching
Assistant:
Juan Guevara
Hours: M-T, 11:00 a.m. - 2:00 p.m.
Schedule: MW, 9:30 a.m. - 10:45 a.m., Zoom
Book:Introduction to the Theory of Computation. M. Sipser, 3rd edition, 2012.
Syllabus:CSCI4325_syllabus.pdf
Final:December 9th, 8:00 a.m. - 9:45 a.m., ONLINE

Schedule / Topics

Week M W
08/24 - 08/26 Course overview (notes) Discrete review/Languages (notes)
08/31 - 09/02 DFAs/Regular Languages (notes) DFAs/Regular Languages (notes)
09/07 - 09/09 No class NFAs (notes)
09/14 - 09/16 NFAs (notes) Regex (notes)
09/21 - 09/23 Non-Regular Languages (notes) Non-Regular Languages (notes)
09/28 - 09/30 CFGs (notes) CFGs (notes)
10/05 - 10/07 PDAs (notes) non-CFLs (notes)
10/12 - 10/14 TMs (notes) TMs/Decidability (notes)
10/19 - 10/21 Multitape/NTM (notes) Hilbert (notes)
10/26 - 10/28 Decidability (notes) Decidability (notes)
11/02 - 11/04 Uncountability (notes) Undecidability (notes)
infinity
11/09 - 11/11 Reductions (notes) Complexity (notes)
11/16 - 11/18 Exam Complexity (notes)
11/23 - 11/25 P and NP (notes) Thanksgiving
11/30 - 12/02 Reductions Reductions
12/07 - 12/09 No class Final Exam

Assignments

Due Date Assignment
1 - ?/? hw1.pdf
2 - 9/18 hw2.pdf
3 - 9/23 hw3.pdf
4 - 10/05 hw4.pdf
5 - 11/02 hw5.pdf
6 - 12/04 hw6.pdf

Bonus

There are many ways to receive bonus in the class:

Bonus Reading

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 Self-Assembly and Polyomino Context-Free Grammars CFGs, yay!
9 A Simple Proof for the NP-Hardness of Edge Labeling One of the best explanations for planar 3SAT reductions.

Resources

Additional reading material:

Puzzle related stuff:
Rubik's cube video

Resources: