Monash University Handbook 2010 Undergraduate - Unit

FIT3014 - Analysis and design of algorithms

6 points, SCA Band 2, 0.125 EFTSL

Level	Undergraduate
Faculty	Faculty of Information Technology
Offered	Clayton First semester 2010 (Day) Clayton Second semester 2010 (Day) Sunway First semester 2010 (Day)
Coordinator(s)	Associate Professor Graham Farr

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 strategy 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

At the completion of this unit students will have -
A knowledge and understanding of:

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.

Developed attitudes that enable them to:

be sensitive to the implications algorithm design has for computational complexity;
be aware of the appropriateness of different search methods for different problems.

Developed the skills to:

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.

Assessment

Examination (3 hours): 60%; In-semester assessment: 40%

Chief examiner(s)

Associate Professor Graham Farr

Contact hours

2 hrs lectures/wk, 2 hrs laboratories/wk