CPSC 326: Theoretical Foundations of Computing

Course Description

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.

Course Goals & Objectives

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

Grading Policy

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

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

Honor Policy

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!

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.

Teams

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:

• Section 1 Teams
• Section 2 Teams

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.

Tentative Schedule

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