AI-217-paul.wilmoth-2026-08-20-01-13-04
Title of Course [Theory of Computation for AI]
Prefix and Number [AI 217]
Semester and Year [tbd]
Number of Credit Hours [3]
Prerequisites [AI 142 or CPTS 122]
Course Details
Day and Time: [tbd]
Meeting Location: [tbd]
Instructor Contact Information
Instructor Name: [tbd]
Instructor Contact Information: [office location, phone, email] [tbd]
Instructor Office Hours: [click here for best practices] [tbd]
TA Name: [tbd]
TA Contact Information: [office location, phone, email]: [tbd]
TA Office Hours: [click here for best practices] [tbd]
Course Description
The course develops the discrete mathematical and formal computational foundations needed to analyze artificial intelligence systems. Topics include logic, sets, relations, functions, proof techniques, combinatorics, graphs, trees, finite automata, regular expressions, context-free grammars, Turing machines, decidability, reductions, and introductory computational complexity. Students use formal reasoning and computational modeling to represent AI-relevant problems, recognize structured inputs, analyze computational capabilities and limitations, and explain why some AI problems require heuristic, approximate, or resource-aware approaches.
Course Materials
Books: No single text book is required. Selected readings may be drawn from Michael Sipser, Introduction to the Theory of Computation, 3rd edition; Kenneth Rosen, Discrete Mathematics and Its Applications; and the freely available Mathematics for Computer Science by Eric Lehman, F. Thomson Leigthon, and Albert Meyer.
Other Materials: Students will use Python and Jupyter Notebook for small computational demonstrations and a modeling tool such as JFLAP or an equivalent instructor-selected tool. Graph visualization software such as Graphviz may also be used. Instructor-provided notes, worksheets, examples, and software documentation will be available through Canvas. All required software will be open source or institutionally provided.
Fees: None
|
Course Learning Outcomes (students will be able to:) |
Activities Supporting the Learning Outcomes | Assessment of the Learning Outcomes |
|---|---|---|
| 1. Use formal logic, sets, relations, functions, and proof techniques to express and justify claims about discrete computational systems (1e). | Lectures; guided workshops; logic exercises; collaborative problem solving | Problem sets; quizzes; midterm examination; proof portfolio |
| 2. Apply combinatorial reasoning, graphs, trees, recursion, and induction to model and analyze AI-relevant structures and processes (1e). | Graph-modeling laboratories; counting exercises; recursion and induction activities; AI examples | Problem sets; modeling laboratory; Applied Assignment 1; examinations |
| 3. Model finite-state computational processes using regular expressions, deterministic finite automata, and nondeterministic finite automata (1e). |
Automata demonstrations; JFLAP or equivalent laboratories; state-machine design exercises |
Formal modeling laboratory; Applied Assignment 2; quizzes; examinations |
| 4. Construct context-free grammars and parse trees for structured inputs and explain the role of pushdown automata (1e). |
Grammar-design workshops; parsing exercises; structure-language examples |
Problem sets; grammar laboratory; Applied Assignment 2; quizzes; examinations |
| 5. Explain Turing machines and distinguish among recognizable, decidable, and undecidable problems (1e). | Machine simulations; conceptual demonstrations; guided constructions; case analyses | Problem sets; quizzes; Applied Assignment 3; final examination |
| 6. Use introductory reductions and complexity classes to analyze the computability and tractability of computational problems (1e). |
Reduction workshops; complexity analysis activities; worked examples |
Problem sets; Applied Assignment 3; synthesis case study; final examination |
| 7. Communicate how formal methods and computational limits influence the design, evaluation, and responsible interpretation of AI systems (3b, 6e). | AI theory case studies; technical writing; peer review; presentations | Synthesis case study; written explanation; presentation; final examination |
| Dates | Lesson Topic | Assignment or Activity | Assessment |
|---|---|---|---|
|
Week 1 |
Propositions, predicates, quantifiers, and formal AI statements | Logic worksheet; specification activity | Diagnostic activity |
| Week 2 | Sets, relations, functions, and discrete representations | Representation laboratory | Problem Set 1 |
| Week 3 | Proof techniques, counterexamples, and mathematical induction | Guided proof workshop | Quiz 1 |
| Week 4 |
Recursion, counting, and combinatorial growth | State-space counting activity | Applied Assignment 1 begins |
| Week 5 |
Graphs, trees, reachability, and AI structures | Graph-modeling laboratory | Applied Assignment 1 |
| Week 6 |
Strings, formal languages, and regular expressions | Language and pattern laboratory | Problem Set 2 |
| Week 7 |
Deterministic and nondeterministic finite automata | Automata-design laboratory | Applied Assignment 2 begins |
| Week 8 |
Review and synthesis of discrete structures and regular expressions | Guided review activities | Midterm examination |
| Week 9 |
Finite-automata equivalence, closure, and limits of regular expression | Recognizer comparison activity | Applied Assignment 2 |
| Week 10 |
Context-free grammars, derivations, parse trees, and pushdown-automata concepts | Grammar-design laboratory | Problem Set 3 |
| Week 11 | Turing machines, recognition, decision, and universal computation | Turing-machine simulation | Quiz 2 |
| Week 12 |
Decidability, the halting problem, and introductory reductions | Reduction workshop | Applied Assignment 3 begins |
| Week 13 |
Computational resources, tractability, P, and NP | Complexity classification activity | Applied Assignment 3 |
| Week 14 |
Computational limits in AI; exact, heuristic, and approximate approaches | AI theory case-study workshop | Synthesis case study begins |
| Week 15 |
Course integration and communication of theoretical limits | Case-study presentation and review | Synthesis presentation |
| Finals week | Comprehensive synthesis | Final case-study submission | Final examination |
Expectations for Student Effort
For each hour of lecture equivalent, students should expect to have a minimum of two hours of work outside of class.
Grading
| Assignment Category | Description | Weight |
|---|---|---|
| Problem sets and quizzes | Formal reasoning, proofs, discrete modeling, automata, computability, and complexity exercises | 25% |
| Formal modeling laboratories | Guided graph, automata, grammar, and Turing machine modeling activities | 10% |
| Three applied theory assignments | Scaffolded assignments connecting discrete structures, formal languages, and computational limits of AI | 25% |
| Midterm examination | Logic, proof, combinatorics, graphs, formal languages, and finite automata | 15% |
| AI theory synthesis case study | Analysis and communication of a selected AI problem using course theory | 10% |
| Final examination | comprehensive formal reasoning, computability, and complexity assessment | 15% |
| Total | 100% |
| Grade | Percent | Grade | Percent |
|---|---|---|---|
| A |
93 -- 100% |
C | 70 -- 76.99% |
| A- | 90 -- 92.99% | C- | 67 -- 69.99% |
| B+ | 87 -- 89.99% | D | 60 -- 66.99% |
| B | 83 -- 86.99% | F | less than 60% |
| B- | 80 -- 82.99% | ||
| C+ | 77 -- 79.99% |
Attendance and Make-Up Policy
Students should make all reasonable efforts to attend all class meetings. However, in the event a student is unable to attend a class, it is the responsibility of the student to inform the instructor as soon as possible, explain the reason for the absence (and provide documentation, if appropriate), and make up class work missed within a reasonable amount of time, if allowed. Missing class meetings may result in reducing the overall grade in the class.
Academic Integrity Statement
You are responsible for reading WSU's Academic Integrity Policy, which is based on Washington State law. If you cheat in your work in this class you will:
-Fail in the assignment or exam in which the cheating happened
-Be reported to the Center for Community Standards
-Have the right to appeal my decision
-Not be able to drop the course of withdraw from the course until the appeals process is finished
If you have any questions about what you can and cannot do in this course, ask me.
If you want to ask for a change in my decision about academic integrity, use the form at the Center for Community Standards website. You must submit this request within 21 calendar days of the decision.