Algorithms and Complexity

The aim of this subject is for students to develop familiarity and competence in assessing and designing computer programs for computational efficiency. Although computers manipulate data very quickly, to solve large-scale problems, we must design strategies so that the calculations combine effectively. Over the latter half of the 20th century, an elegant theory of computational efficiency developed. This subject introduces students to the fundamentals of this theory and to many of the classical algorithms and data structures that solve key computational questions. These questions include distance computations in networks, searching items in large collections, and sorting them in order.

• 1Design, manipulate and reason about a variety of techniques for solving sorting, searching and graph problems
• 2Write efficient algorithms and data structures for a variety of fundamental problems
• 3Conduct formal reasoning about problem complexity and algorithmic efficiency
• 4Recognize the design techniques of standard algorithms, and apply these techniques to develop new computational solutions to problems