FIT3014 - Analysis and design of algorithms

Leader: Associate Professor David Dowe

Offered

Clayton First semester 2008 (Day)
Clayton Second semester 2008 (Day)
Sunway First semester 2008 (Day)

Synopsis

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.

Objectives

1. Advanced deterministic search strategies, including A*'
2. Advanced stochastic search and optimization techniques, including simulated annealing, genetic algorithms and Markov Chain Monte Carlo;
3. Monte Carlo simulation methods for estimation and problem solving;
4. Probability theory and basic information theory;
5. Methods for analysing algorithmic complexity, including asymptotic notation and average case complexity;
6. Dynamic programming concepts and methods;
7. Basic computational complexity theory, including nondeterministic Turing machines, P reduction, NP-Completeness;
8. Be sensitive to the implications algorithm design has for computational complexity;
9. Be aware of the appropriateness of different search methods for different problems;
10. Select a search strategy appropriate to a given problem;
11. Analyse the computational complexity of search algorithms;
12. Employ Monte Carlo simulation techniques;
13. Determine when dynamic programming methods will assist in dealing with resource limits;
14. Use basic statistics to estimate program behaviour;
15. Develop asymptotic approximations to computationally complex problems.

Assessment

Assignments: 30%
Compulsory assessed laboratory classes: 10%
Examination (3 hours): 60%

Contact hours

4 x contact hrs/week

Prerequisites

FIT2004 or CSE2304

Prohibitions

CSE3305