COMP473 : Advanced Algorithms
Semester 1, 2010
Faculty: Science; Department: Computing
Convenor: Mark Dras
Students should read this unit outline carefully at the start of semester. It contains important information about the unit. If anything in it is unclear, please consult one of the teaching staff in the unit.
About This Unit
Many problems are impossible to solve exactly in a computationally tractable manner: NP-complete problems such as the vertex cover of a graph fall into this category, which has relevance to real-world applications. Possible solutions are to use approximation methods or to use heuristic approaches; of the latter there are many alternatives, such as neural networks, simulated annealing, and so on.
This unit will cover issues of computational complexity related to these types of problems, different types of methods for devising algorithms to solve computationally difficult problems -- approximation methods, randomization methods, heuristic approaches such as genetic programming or ant colony optimisation, and probabilitistic approaches -- and also how these are applied to real-world problems, such as network routing or mobile keyboard design.
Teaching Staff
| Role | Name | Webpage | Room | Office hours |
|---|---|---|---|---|
| Convener, Lecturer | Mark Dras | http://www.comp.mq.edu.au/~madras | E6A380 | by appointment |
| Lecturer | Bernard Mans | http://www.comp.mq.edu.au/~bmans/ | E6A362 | by appointment |
Lectures
Each week you should attend two to three hours of lectures. The nominated time is Mon 4:00pm-7:00pm.
Required Texts
There's no required text. There will be lecture notes each week, plus some required reading in the form of papers.
Required Technology
None.
Unit Web Page
The web page for this unit can be found at http://www.comp.mq.edu.au/units/comp473/.
Learning Outcomes
A student completing the unit should have:
- An understanding of issues involved in computationally difficult problems (such as theoretical instances like the travelling salesperson or set cover, and practical instances like determining the layout of mobile phone keypads).
- An understanding of metaheuristic approaches to these problems.
- An understanding of approximation approaches to these problems.
- Experience of implementing solutions to a particular problem instance.
- Experience in presenting on these problems.
In addition to the discipline-based learning objectives, all academic programs at Macquarie seek to develop students' generic skills in a range of areas. One of the aims of this unit is that students develop their skills in the following:
- Foundation skills of literacy, numeracy and information technology;
- Self-awareness and interpersonal skills;
- Communication skills;
- Critical analysis skills;
- Problem-solving skills;
- Creative thinking skills.
Topic List
See the Lectures page.
Assessment
See the Assignments and Exercises page.