Home CPSC 326

CPSC 326: Theoretical Foundations of Computing

Meeting Times:Section 1: Monday and Wednesday 9:00 - 10:50
Section 2: Monday and Wednesday 1:00 - 2:50
Instructor:Ian Finlayson
Office:Trinkle B18
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.

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

To gain an understanding of:

Grading Policy

Your grade will be determined as follows: The grading scale used for this course is as follows:

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

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 Lee Hall, Room 401.


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.

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

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.