CSC236H1: Introduction to the Theory of Computation


The application of logic and proof techniques to Computer Science. Mathematical induction; correctness proofs for iterative and recursive algorithms; recurrence equations and their solutions; introduction to automata and formal languages. This course assumes university-level experience with proof techniques and algorithmic complexity as provided by CSC165H1. Very strong students who already have this experience (e.g. successful completion of MAT157Y1) may consult the undergraduate office about proceeding directly into CSC236H1 or CSC240H1.


60% or higher in CSC148H1/​ 60% or higher in CSC111H1, 60% or higher in CSC165H1/​ 60% or higher in CSC111H1 (Please note: The minimum prerequisite grade in CSC148H1 and CSC165H1/​CSC240H1 is lower than the minimum grade for program admission in Computer Science. If you take this course when your grade in CSC165H1/​CSC240H1 is lower than the requirement for program admission, you will be unable to enrol in a Computer Science program. If you hope to enrol in a Computer Science program in future, please ensure that you satisfy the program admission grade requirements in CSC165H1/​CSC240H1 before completing CSC236H1. Students will not be permitted to retake CSC165H1 after completing CSC236H1.)

Distribution Requirements: 
Breadth Requirements: 
The Physical and Mathematical Universes (5)