CMPUT 474 Winter 2025 The Nature of Computation
Overview
This course will investigate the fundamental nature of computation, addressing the basic questions of what is (and is not) computable, what can (and cannot) be computed efficiently, and what consequences follow from certain machine and programming language restrictions. After an introduction to the foundations of computing and its relation to mathematics, the course will investigate finite state automata, regular languages, stack-augmented automata, context free languages, Turing machines, computability, recursive functions, the limits of mathematical reasoning, computational complexity, the classes P, NP and PSPACE, NP-completeness, and the complexity hierarchy.
Objectives
To understand and appreciate the fundamental nature of computation and the limits of mathematical reasoning.
Pre-requisites
CMPUT 204 or 275, one of CMPUT 229, EE 380 or ECE 212 and one of MATH 225, 227 or 228, or consent of the instructor.
Course Topics
The fundamentals of computation and mathematical reasoning, computability, complexity, restricted models of computation.
Course Work and Evaluation
Four assignments
Midterm exam (covers first half of the course)
Final exam (covers second half of the course)
Course Work Weight
Assignment 1 10%
Assignment 2 10%
Midterm exam 30%
Assignment 3 10%
Assignment 4 10%
Final exam 30%
Course Materials
Textbook:
Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser
Book website