Course Information

Instructor: Tim Wylie
ENGR 3.287
956-665-2577
timothy.wylie@utrgv.edu
Schedule: MW, 9:25 a.m. - 10:40 a.m., ENGR 1.272
Book:Introduction to the Theory of Computation. M. Sipser, 3rd edition, 2012.
Syllabus:CSCI4325_syllabus.pdf
Final:December 13th, 8:00 a.m. - 9:45 p.m., ENGR 1.272

Schedule / Topics

w
Week M W
08/28 - 08/30 Course overview (n01) Sets (p02)
09/04 - 09/06 No Class Functions (p03)
09/11 - 09/13 DFAs/Regular Languages (p04) DFAs/Regular Languages (p05)
09/18 - 09/20NFAs (p06) NFAs (p07)
09/25 - 09/27 Regular Expressions (p08) Non-Regular Languages (p09)
10/02 - 10/04 Non-regular languages (p10) CFGs (none)
10/09 - 10/11 CFGs (p12) PDAs
10/16 - 10/18 PDAs
Test
10/23 - 10/25 TMs TM
10/30 - 11/01 TM
Decidability
11/06 - 11/08 Decidability Infinities
11/13 - 11/15 Undecidability
Undecidability
11/20 - 11/22 Reductions
Test
11/27 - 11/29 Time Complexity
P/NP
12/04 - 12/06 Dealing with NP-hardness Reductions/Space Complexity
12/11 - 12/13 No Class Final

Assignments

Due Date Assignment
1 - TBD hw1.pdf
2 - 10/27 hw2.pdf
3 - 10/2 hw3.pdf
4 - 10/16 hw4.pdf
5 - 10/18 hw5.pdf

Bonus

There are six ways to receive bonus in the class:

Bonus Reading

Post Date Paper Instructions
1 - 8/28 Computer solution to the 17-point Erdos-Szekeres problem
2 - 9/11 Logicomix A fun graphic novel about Bertrand Russell and first-order logic
3 - 9/11 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.
4 - 10/20 Combinatorial Optimization Problems in Self-Assembly

Resources

Additional reading material:

Puzzle related stuff:
Rubik's cube video

Resources: