CPSC 326: Theoretical Foundations of Computing

Course Description

Covers structures and concepts relating to the underlying theory of computation and mathematical models of actual physical processes. Also covers a repertoire of advanced algorithms for data processing, and the asymptotic analysis of those algorithms to describe their running time and space requirements. Topics may include formal languages, automata theory, Turing machines, the halting problem, NP completeness, searching and traversal algorithms, dynamic programming, compression algorithms, and random number generation.

Course Goals & Objectives

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

Student Learning Outcomes

After completing this course, students will be able to:

• Discuss the concept of finite state machines.
• Design a deterministic finite state machine to accept a specified language.
• Generate a regular expression to represent a specified language.
• Explain why the halting problem has no algorithmic solution.
• Design a context-free grammar to represent a specified language.
• Define the classes P and NP.
• Explain the significance of NP-completeness.

Class Format

For each class period, there will be an assigned reading from GEB. Most days will start with a reading quiz on that day's reading, and recent material. The goal of the quizzes is to make sure you're keeping up with the reading and material. The book is long, but reading it is your only assigned out-of-class work for this course.

We will then go over concepts and material, and work problems together as a class. Then, we will practice this material by working on problems in teams. The teams are chosen at the beginning of the semester and will not change. Your team will work on these problems and then turn in your work by the end of the class period.

We will also have a final, cumulative exam at the end of the semester.

Grading Policy

This class will used an XP-based grading scale. Each quiz is worth 15 points. Each in-class team assignment is worth 25 points (for everyone on the team). The final exam is worth 100 XP. I may add additional XP opportunities at my discretion.

Your final grade will be calculated using the following table:

Makeup quizzes and team assignments will be given if you let me know you will miss a class ahead of time, or in the event of sickness or emergency. (Though you will need to do make-up team assignments alone).

The University provides the opportunity to provide grading feedback midway through the semester. This will take into account your XP up to that point. Any student receiving less than a 300 at that point 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.

Student Conduct

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

Honor Policy

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

For quizzes and the final exam, you can not talk to anyone, use the book, or use any kind of notes.

For team assignments, you can work only with your team and cannot search for the answer or ask an LLM.

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

Statement on Class Recordings

Classroom activities in this course may be recorded by students enrolled in the course for the personal, educational use of that student only, and may not be further copied, distributed, published or otherwise used for any other purpose without the express written consent of the course instructor. All students are advised that classroom activities may be taped by students for this purpose. Distribution or sale of class recordings is prohibited without the written permission of the instructor and other students who are recorded. Distribution without permission is a violation of copyright law. This policy is consistent with UMW's Policy on Recording Class and Distribution of Course Materials.

Statement on Digital Accessibility of Course Materials

I have made every effort to ensure that all digital content, documents, and multimedia in this course meet current ADA standards and accessibility guidelines. My goal is to ensure that all materials are us- able by all students from day one. If you encounter any content that is not accessible, please contact me immediately. I will work with the school to resolve the issue or provide an equally effective alternative format as quickly as possible. If you require specific academic accommodations due to a documented disability, please contact the Office of Disability Resources.

Disability Statement

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.

Tentative Schedule

Date	GEB Reading	Class Topic
August 25		Course Introduction, Finite Automata
August 27	Introduction: A Musico-Logical Offering	More Finite Automata
September 1	Three-Part Invention, Chapter I: The MU-puzzle	Non-Determinism
September 3	Two-Part Invention, Chapter II: Meaning and Form in Mathematics	DFA-NFA Equivalence
September 8	Sonata for Unaccompanied Achilles, Chapter III: Figure and Ground	Regular Expressions
September 10	Contracrostipunctus, Chapter IV: Consistency, Completeness, and Geometry	Regular Expressions Continued
September 15	Little Harmonic Labyrinth	Non-Regular Languages
September 17	Chapter V: Recursive Structures and Processes	Context-Free Grammars
September 22	Canon by Intervallic Augmentation, Chapter VI: The Location of Meaning	Context-Free Grammars Continued
September 24	Chromatic Fantasy, And Feud, Chapter VII: The Propositional Calculus	Propositional Calculus
September 29	Crab Canon, Chapter VIII: Typographical Number Theory	TNT
October 1	A Mu Offering	Push-Down Automata
October 6	Chapter IX: Mumon and Gödel	Non-Context-Free Languages
October 8	Prelude ..., Chapter X: Levels of Description, and Computer Systems	Turing Machines
October 13	Fall Break
October 15	... Ant Fugue	Turing Machine Variants
October 20	Chapter XI: Brains and Thoughts	Turing Machines Continued
October 22	English French German Suit, Chapter XII: Minds and Thoughts	The Church-Turing Thesis
October 27	Aria with Diverse Variations	Decidability
October 29	Chapter XIII: BlooP and FlooP and GlooP	Reducibility and Undecidability
November 3	Election Day
November 5	Air on G's String, Chapter XIV: On Formally Undecidable Propositions ...	Complexity Theory
November 10	Birthday Cantatatata ..., Chapter XV: Jumping out of the System	Complexity & P
November 12	Edifying Thoughts of a Tobacco Smoker	The Class NP
November 17	Chapter XVI: Self-Ref and Self-Rep	The Recursion Theorem
November 19	The Magnificrab, Indeed, Chapter XVII: Church, Turing, Tarski, and Others	NP-Completeness
November 24	SHRDLU, Toy of Man's Designing, Chapter XVIII: AI Retrospects	More NP-Complete Problems
November 26	Thanksgiving Break
November 26	Thanksgiving Break
December 1	Contrafactus, Chapter XIX: AI Prospects	Space Complexity
December 3	Sloth Canon, Chapter XX: Strange Loops, Or Tangled Hierarchies	Catchup and Review
December 8	Six-Part Ricercar	Final Exam, 8:30 – 11:00