Algorithms and complexity

Description

AIMS 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. INDICATIVE CONTENT 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. Teaching Period: 2 March 2026 to 31 May 2026 Assessment Information: Description Timing Percentage Project work during semester due around weeks 7 and 11, addressing all Intended Learning Outcomes (ILOs) 1-4. 30-36 hours (of work required) From Week 7 to Week 11 30% 10 weekly online quizzes, addressing ILOs 1 and 3. 30 minutes (each) Throughout the teaching period 10% A written closed book examination, addressing all Intended Learning Outcomes (ILOs) 1-4. 3 hours Hurdle requirement: The examination is a hurdle and must be passed to pass the subject During the examination period 60%