41080 Theory of Computing Science6cp; 3hpw, on campus. Forms of attendance and mode of delivery in this subject have changed to enable social distancing and reduce the risks of spreading COVID-19 in our community.
Requisite(s): 37181 Discrete Mathematics AND 48024 Applications Programming
This subject introduces the theory of computation, including topics from the theories of automata, rewriting, and parsing. Students learn to compute orders of complexity for various practical problems.
An understanding of computational complexity can lead to the design of economical and feasible products and services. For example, for an online taxi service, strategically simplifying the computation can dramatically reduce the cost of solving the very large-scale passenger-driver matching problem.
Similarly, mastering the fundamental theory of computation enables one to construct security schemes that are both convenient for users and tough against attackers. Also, in programming, the knowledge of how high-level statements are translated into operational instructions helps one identify performance bottlenecks to achieve optimal efficiency by appropriate design of the algorithm.
Spring session, City campus
Detailed subject description.