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 (p13)
10/16 - 10/18 PDAs (p14) Test
10/23 - 10/25 TMs (p15) TMs (p16)
10/30 - 11/01 TM (p17) Decidability (p18)
11/06 - 11/08 Decidability (p19) Undecidability (p20)
11/13 - 11/15 Undecidability Undecidability (p22)
11/20 - 11/22 Reductions (p23) Test
11/27 - 11/29 Time Complexity (p24) P/NP (p25)
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
6 - 11/13 hw6.pdf
7 - 11/22 hw7.pdf
8 - 12/13 hw8.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: