Authorised by Academic Registrar, April 1996
Objectives At the completion of this subject students should have developed competence in techniques for analysing an algorithm to estimate its computational time complexity, together with an understanding of the approximations made in obtaining such estimates; be able to apply these techniques to algorithms of practical importance in computing, such as sorting and searching algorithms; and appreciate how time complexity analysis can reveal an algorithm to be intractable, and the practical consequences of this.
Synopsis Time complexity functions, dominant operations, worst case analysis, rates of growth of functions, O(f) notation, addition and multiplication algorithms, Karatsuba's method, searching and sorting algorithms, parallel computation, polynomial and exponential algorithms, NP-completeness.
Assessment Examination (2 hours): 70% + Assignments (3): 30%