Theory of Computation (COMP711)

(01/09/2023-03/05/2023)

Course Memo

The learning objectives of this course are to: 1) introduce students to the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability and 2) enhance/develop students' ability to understand and conduct mathematical proofs for computation and algorithms. Upon successful completion of this course, students will be able to a) discuss key notions of computation, such as algorithm, computability, decidability, reducibility, and complexity, through problem solving. b) explain the models of computation, including formal languages, grammars and automata, and their connections. c) state and explain the Church-Turing thesis and its significance. d) analyze and design finite automata, pushdown automata, Turing machines, formal languages, and grammars. e) solve computational problems regarding their computability and complexity and prove the basic results of the