FIT3014 - Analysis and design of algorithms
6 points, SCA Band 2, 0.125 EFTSL
Undergraduate Faculty of Information Technology
Leader(s): Associate Professor David Dowe
This unit provides students with advanced techniques for designing and analysing complex algorithms. In particular, it teaches advanced search strategies, how to select an appropriate search stategy for a given problem, advanced techniques for analysis of algorithmic complexity, dynamic programming, basic statistics to estimate program behaviour, Monte Carlo simulation techniques, and basic notions in computability such as NP completeness.
- Advanced deterministic search strategies, including A*'
- Advanced stochastic search and optimization techniques, including simulated annealing, genetic algorithms and Markov Chain Monte Carlo;
- Monte Carlo simulation methods for estimation and problem solving;
- Probability theory and basic information theory;
- Methods for analysing algorithmic complexity, including asymptotic notation and average case complexity;
- Dynamic programming concepts and methods;
- Basic computational complexity theory, including nondeterministic Turing machines, P reduction, NP-Completeness;
- Be sensitive to the implications algorithm design has for computational complexity;
- Be aware of the appropriateness of different search methods for different problems;
- Select a search strategy appropriate to a given problem;
- Analyse the computational complexity of search algorithms;
- Employ Monte Carlo simulation techniques;
- Determine when dynamic programming methods will assist in dealing with resource limits;
- Use basic statistics to estimate program behaviour;
- Develop asymptotic approximations to computationally complex problems.
Compulsory assessed laboratory classes: 10%
Examination (3 hours): 60%
4 x contact hrs/week
FIT2004 or CSE2304