This module provides students with an introduction to the analysis of algorithms specifically proving their correctness and making a statement about their efficiency. Topics for discussion may include loop invariants, strong mathematical induction and recursion, asymptotic notation, recurrence relations and generating functions. Students examine examples of algorithm analysis from searching and sorting algorithms. Second part of the module concentrates on classification of algorithms and building a strong knowledge base of existing algorithms.
Prerequisites
CSD 2126, CSD 2183, CSD 2201