Meeting Times: | Section 1: Monday and Wednesday 9:00 - 10:50 Section 2: Monday and Wednesday 1:00 - 2:50 |

Instructor: | Ian Finlayson |

Email: | ifinlay@umw.edu |

Office: | Farmer B47 |

Office Phone: | 540-654-1714 |

Office Hours: | Monday and Wednesday 11:00 - 12:00, Tuesday and Thursday 9:00 - 10:00, Friday 9:00 - 11:00. |

Required Textbook: | Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. |

Emphasis will be on structures and concepts relating to the theory of computation and the different types of theoretical machines that are mathematical models for actual physical processes. Topics may include automata theory, Turing machine theory, formal language theory, and the halting problem.

- The theoretical machines which are mathematical models for actual physical processes.
- Turing machines.
- The halting problem.
- Formal language theory.

- Assignments, 30%
- Quizzes, 30%
- Final Exam, 20%
- Participation, 20%

- [94, ∞): A
- [90, 94): A-
- [87, 90): B+
- [84, 87): B
- [80, 84): B-
- [77, 80): C+
- [72, 77): C
- [70, 72): C-
- [66, 70): D+
- [60, 66): D
- [0, 60): F

Late assignments will have a 10% reduction in grade for each day late. There will be no make up for missed quizzes, though your lowest quiz grade will be dropped. Final grades will not be rounded up, and no extra credit opportunities will be given on an individual basis.

The University provides the opportunity to provide grading feedback midway through the semester. This will take into account your score on the mid-term exam and the programming projects submitted up to that point. Any student receiving less than a 65% on either of these will receive a "U" for their mid-semester grade. If this happens to you, please don't hesitate to talk with me about how we can improve your performance in this class.

- You are expected to attend each class meeting. If you miss a class, you are responsible for the material covered.
- You are asked not to use laptops or cell phones during class time.
- This class will be interactive. Expect to answer questions in class and always feel free to ask any questions yourself.
- If you miss an exam, you are required to provide legitimate documentation of an emergency for your absence to have a make up exam.
- If you can't make an exam for a non-emergency reason, you must schedule an alternate time to take it ahead of time.

Students are expected to conduct themselves in a manner consistent with the letter and spirit of the Honor Constitution.

**For assignments**, you may discuss the ideas with other students, but
all of your work must be your own. You must yourself write and understand
everything in each assignment you submit. It is an honor code violation to
copy directly from another student either by copy and paste or by
transcription, or to copy from the web.

**For quizzes and exams**, you can not talk to anyone during the exam, or
use any kind of notes.

If you have any questions or need clarification, please don't hesitate to contact me!

The Office of Disability Services has been designated by the University as the primary office to guide, counsel, and assist students with disabilities. If you already receive services through the Office of Disability Services and require accommodations for this class, make an appointment with me as soon as possible to discuss your approved accommodations needs. Please bring your accommodation letter with you to the appointment. I will hold any information you share with me in the strictest confidence unless you give me permission to do otherwise. If you have not contacted the Office of Disability Services and need accommodations, I will be happy to refer you. The office will require appropriate documentation of disability. Their phone number is 540-654-1266. The office is located in Seacobeck Hall.

Most class periods will begin with a lecture on some topic where we will go over new course material. Then, we will practice this material by working on problems in teams. The teams are chosen randomly at the beginning of the semester and will not change. Your team will work on these problems and then we will discuss them together as a class.

Teams for the two sections are given here:

At the end of each such class period, you will turn in your team's answers to be graded for completion as part of your participation grade.

Date | Class Topic | GEB Reading | Team Assignment | Assignment Due |

January 17 | Course Introduction, Finite Automata | DFAs | ||

January 22 | More Finite Automata | Introduction, Chapter I | DFA Languages | |

January 24 | Non-Determinism | NFAs | ||

January 29 | DFA-NFA Equivalence | Chapter II, III | ||

January 31 | Regular Expressions | Regular Expressions | ||

February 5 | Regular Expressions Continued | Chapter IV | ||

February 7 | Non-Regular Languages | Non-Regular Languages | ||

February 12 | Context-Free Grammars | Chapter V | ||

February 14 | Context-Free Grammars Continued | Context-Free Grammars | ||

February 19 | Push-Down Automata | Chapter VI | Problem Set 1 | |

February 21 | No Class | |||

February 26 | Non-Context-Free Languages | Chapter VII | ||

February 28 | Turing Machines | Turing Machines | ||

March 5 | Spring Break | |||

March 7 | ||||

March 12 | Turing Machine Variants | Chapter VIII, IX | ||

March 14 | Turing Machines Continued | More Turing Machines | ||

March 19 | The Church-Turing Thesis | Chapter X | Problem Set 2 | |

March 21 | Snow Day | |||

March 26 | No class | |||

March 28 | Decidability | Chapter XIII | Decidable Problems | |

April 2 | Reducibility and Undecidability | Chapter XIV | ||

April 4 | The Recursion Theorem | |||

April 9 | Complexity Theory | Chapter XV | Complexity Theory | |

April 11 | Complexity & P | |||

April 16 | The Class NP | Chapter XVII | ||

April 18 | NP-Completeness | Problem Set 3 | ||

April 23 | More NP-Complete Problems | Chapter XX | ||

April 25 | Final Exam Topic List | Final Practice Problems | ||

May 4 | 8:30 - 11:00, Section 1 Final Exam | |||

12:00 - 2:30, Section 2 Final Exam |

Copyright © 2022 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.