Algorithms and computational complexity
4 points * 2 hours of classes per week * Second semester * Caulfield * Prerequisites: Any first-year mathematics subject
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: 30%
Recommended texts
Baase S Computer algorithms: Introduction to design and analysis 2nd edn, Addison-Wesley, 1988
| Published by Monash University, Clayton, Victoria
3168 Copyright © Monash University 1996 - All Rights Reserved - Caution Authorised by the Academic Registrar December 1996 |