Deterministic Time
Overview
Initial lectures introduce a version of the model of computation that will be used in much of this course — a Turing machine — along with the use of simulations to compare the computational power of different machine models. They also introduce properties of deterministic computation, and deterministic time-complexity classes, that will be used throughout the course.
The notions of reductions are then introduced. While these can be presented using the infomrmation about deterministic computation that has been provided so far, these will be used throughout most of the rest of this course.
Quite a bit of this material has already been introduced in the computer science program — notably, in CPSC 313 and CPSC 413. CPSC 511/611 will provide additional detail and will include more advanced material that is generally not covered in these prerequisite courses.
