Algorithms and computational complexity
P Grossman
4 points
* 2 hours classes per week
* Second semester
*
Caulfield
* Prerequisites: Any first-year mathematics subject
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%
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 |