COMP473 : Advanced Algorithms
This is the home page for COMP473, Semester 1 2010.
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.