Description
Instructor(s)/Supervisor(s)/Coordinator(s): Maocheng LIThis course is an introduction to the foundation of computation, and aims at answering some of the most fundamental questions in computer science: What is an algorithm? What can and cannot be computed at all? What can and cannot be computed efficiently? The topics covered include set theory and countability, formal languages, finite automata and regular languages, pushdown automata and context-free languages, Turing machines, undecidability, P and NP, NP-completeness.