Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

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