CSCI 4325-01

Automata, Formal Languages, and Computability

Automata, Formal Languages, and Computability

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 |

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/20 | NFAs (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 |

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 |

There are six 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 meeting. Note that papers discussed here will also be included in the bonus papers.
- Additional bonus points are given on exams for each homework assignment you received at least a 'B' on.
- Turning homework in early (before the due date) gives 10% extra.

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 |

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.

Puzzle related stuff:

Rubik's cube video

Resources: