CSCC63H3: Computability and Computational Complexity

Introduction to the theory of computability: Turing machines, Church's thesis, computable and non-computable functions, recursive and recursively enumerable sets, reducibility. Introduction to complexity theory: models of computation, P, NP, polynomial time reducibility, NP-completeness, further topics in complexity theory.
Note: Although the courses CSCC63H3 and CSCC73H3 may be taken in any order, it is recommended that CSCC73H3 be taken first.

CSCB36H3 and CSCB63H3 and [CGPA of at least 3.5, or enrolment in a CSC Subject POSt, or enrolment in a non-CSC Subject POSt for which this specific course is a program requirement]]
CSC363H, CSC365H, CSC364H
Quantitative Reasoning