CSCI 4325

Automata, Formal Languages, and Computability

Automata, Formal Languages, and Computability

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 |

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 |

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 |

There are many ways to receive bonus in the class:

- Do the bonus problems on homeworks and tests.
- Redo test problems you missed and explain them to me for partial credit.
- Read one of the bonus papers listed and write a two page review. Then you meet with me to turn it in and we discuss it. The report should follow this guide to reading papers and writing reviews.
- Attend the Xtreme Algorithms seminar. Note that papers discussed here will also be included in the bonus papers.
- Turning homework in early (before the due date) gives 10% extra.

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. |

Additional reading material:

- How to Prove it: A Structured Approach. Velleman, 2nd edition, 2006.
- Models of Computation. Erickson, J., 2015.
- Introduction to Theory of Computation. Maheshwari, A. and Smid, M., 2016.
- Lecture slides from MIT. Williams, R., 2019.
- Lecture notes from MIT. Aaronson, S., 2008.
- Mathematics and Computation. Wigderson, A., 2019.
- Introduction to Theoretical Computer Science. Barak, B., 2020.

Puzzle related stuff:

Rubik's cube video

Resources: