CPSC 421: Introduction to Theory of Computation

Schedule

Date		Topic
Wed	Sept 9	intro to TCS
Mon	Sept 21	add/drop deadline
Mon	Oct 12	No class: Thanksgiving Day
Mon	Nov 9	No class: midterm break/Remembrance Day
Wed	Nov 11	No class: midterm break

Overview

This is an undergraduate introductory course to the theory of computation. For the first three items below, we will closely follow Introduction to the Theory of Computation (3rd edition) by Sipser [S].

Tentative list of topics:

Finite automata and regular languages [S, Part One, Section 1]
Turing machines and computability theory [S, Part Two, Sections 3-5]
Complexity theory: P, NP, NP-completeness [S, Part Three, Section 7]
Topics in query complexity, information theory, cryptography, randomized and quantum computation

Prerequisites

The formal prerequisites include CPSC 221 and 320. In particular, you should be familiar with [S, Section 0], Big-O and little-o notation, and basic algorithms and discrete math. Some basic knowledge of probability is useful for the topics part of the course but I plan to review it.

Policies

Policies and Resources to Support Student Success. In particular, note the Academic Concession policy, which covers unanticipated events or circumstances such as illnesses. Late policy: late homework or project documents will not be accepted except in cases of Academic Concession. Midterm policy: 50-minute handwritten exam with no notes or calculators allowed. Final exam policy: 2.5 hour handwritten exam with no notes or calculators allowed.

GenAI policy: any use of GenAI is prohibited for homeworks; answers suspected of being from GenAI (for example, by Pangram) will receive zero credit unless you can demonstrate understanding upon appeal.

Template from Danica Sutherland

CPSC 421: Introduction to Theory of Computation (2026W1)

Schedule

Overview

Prerequisites

Policies