Algorithms & Theory
Every single computing device, software, and bits of information is governed by some fundamental laws that remain unchanged regardless of how technology evolves. For instance, regardless of how fast a CPU can get, it cannot take fewer than some number of steps to sort a given list of numbers; There is a limit to the amount of information that a given number of bits can represent; There are computational problems that can never be solved by a computer, and problems that no one knows whether it can be solved efficiently. The study of algorithms and computation theory explores these fundamentals with mathematical rigor, allowing students to gain deep insights into the theoretical underpinnings of computer science and develop software that is resource-efficient.
Primaries
CS3230 Design and Analysis of Algorithms serves as a follow-up to CS2040S Data Structures and Algorithms. In CS3230, students learn the different algorithm design paradigms, techniques to prove the correctness and to analyze the time/space complexity of an algorithm, as well as being introduced to computational complexity classes via the notion of NP-completeness. This course is followed up by CS4231 Parallel and Distributed Algorithms and CS4234 Optimisation Algorithms. CS4231 examines algorithms in the context of where the execution environment is parallelized or distributed; CS4234 examines common techniques for solving optimisation problems and introduces students to methods for finding good-enough solutions to NP-complete problems.
CS4232 Theory of Computation introduces students to mathematical models for abstract computational machines are constructed and their power to solve problems are studied, yielding crucial insights to classes of problems cannot be solved by modern computers regardless of how fast they are. CS3236 Introduction to Information Theory covers the fundamental theory of storing, processing, and communicating information bits. Information theory underlies many modern computer science areas, including compression, networking, and cryptography.
Electives
Students who are algorithmic minded and wish to explore advanced topics in algorithms can consider CS4268 Quantum Computing (algorithms for quantum computers), CS5234 Algorithms at Scale (algorithms on big data), CS5330 Randomized Algorithms (exploiting randomization to be more efficient and correct with high probability), CS5238 Advanced Combinatorial Methods in Bioinformatics (algorithms on gene sequences, phylogenetic tree, gene network, etc).
Other courses provide a theoretical treatment related to security and privacy (CS4257 Algorithmic Foundations of Privacy), game theory (CS4261 Algorithmic Mechanism Design), and logic (CS4269 Fundamentals of Logic in Computer Science). Students can also explore deeper into the theory of computation through CS5230 Computational Complexity and CS5236 Advanced Automata Theory.
