41080 Theory of Computing Science

Description

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.

Typical availability

Spring session, City campus