MAT2492

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