COMP473 : Advanced Algorithms
Lectures
The list below is still tentative.
| Week | Topic | Reading |
|---|---|---|
| 1 | Review of Combinatorial Optimisation Problems | |
| 2 |
Metaheuristics: Ant Colony Optimisation (Revision of algorithm complexity -- notes by Derek Bridge, University College Cork) |
|
| 3 |
Graph Colouring and Ant Colony Optimisation Topics on Problem Hardness |
|
| 4 | Randomised Algorithms: Monte Carlo and Las Vegas |
Jonathan S. Turner (1988). Almost all k-colorable graphs are
easy to color. Journal of Algorithms, 9(1), 63-82.
PDF (need to go via MQ library).
J. A. Ellis and P. M. Lepolesa (1989). A Las Vegas Graph Colouring Algorithm. The Computer Journal, 32(5), 474-476. Oxford Journals PDF. |
| 5 |
Student Presentations Revision of basic stats |
|
| 6 | Parametrised Complexity | |
| 7 | Introduction to Approximation Algorithms | |
| 8 | Approximation Algorithms | |
| 9 | Approximation Algorithms for geometric intersection graphs | |
| 10-11 | Approximation Algorithms for Mobile Network problems | |
| 12 | Presentation of Students' Projects |
References
T. H. Cormen, C. E. Leiserson, R. L. Rivest, & C. Stein, Introduction to Algorithms (MIT Press) second edition. ISBN 0-262-03293-7.