|Look up fees
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.
Topics covered include complexity classes and asymptotic notation; empirical analysis of algorithms; abstract data types including queues, trees, priority queues and graphs; algorithmic techniques including brute force, divide-and-conquer, dynamic programming and greedy approaches; space and time trade-offs; and the theoretical limits of algorithm power.
Intended learning outcomes
On completion of this subject the student should be able to:
- Design, manipulate and reason about a variety of techniques for solving sorting, searching and graph problems
- Write efficient algorithms and data structures for a variety of fundamental problems
- Conduct formal reasoning about problem complexity and algorithmic efficiency
- Recognize the design techniques of standard algorithms, and apply these techniques to develop new computational solutions to problems
On completion of this subject students should have the following skills:
- An ability to apply fundamental knowledge in reasoning and problem solving
- Capacity to reason and solve problems
- Ability to undertake problem identification, formulation and solution
- Capacity for creativity and innovation
- Profound respect for truth and intellectual integrity, and for the ethics of scholarship.
Last updated: 26 February 2024