Introduction to the Theory of Computation Lecture Notes and Exercises

This lecture notes contains following topics: Lecture Notes and
Exercises for CSC, Overview of this Course, Prerequisite Knowledge, The
Induction Idea, Complete Induction, Beyond Numbers, Structural Induction, A
Larger Example, Exercises, Measuring Runtime, A Simple Recursive Function, A
Special Recurrence Form, Quicksort, Exercises, Correctness of Recursive
Programs, Iterative Programs, Termination, Exercises, Regular Languages, A
Suggestive Flowchart, Deterministic Finite Automata, Correctness of DFAs,
Limitations of DFAs, Nondeterminism, Exercises, introduction to the theory of
computation, Concepts from MAT, introduction to the theory of computation

**Author(s):** David Liu Toronto
University

75 Pages