Authorised by Academic Registrar, April 1996
Objectives At the completion of this subject students will be able to develop competence in techniques for analysing an algorithm to estimate its computational time complexity; develop an understanding of the approximations made in obtaining such estimates; apply these techniques to algorithms of practical importance in computing, such as sorting and searching algorithms; gain an appreciation of how time complexity analysis can reveal an algorithm to be intractable, and the practical consequences of this; gain an appreciation of the current state of knowledge in regard to the existence of tractable algorithms for solving problems of practical interest.
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%