| Unit name | Advanced Algorithms |
|---|---|
| Unit code | COMSM1402 |
| Credit points | 10 |
| Level of study | M/7 |
| Teaching block(s) |
Teaching Block 1 (weeks 1 - 12) |
| Unit director | Dr. Jalsenius |
| Open unit status | Not open |
| Pre-requisites | |
| Co-requisites |
None |
| School/department | Department of Computer Science |
| Faculty | Faculty of Engineering |
This unit gives an overview of recent advances in the design of algorithms and data structures. These fall into two broad categories.
First are problems, such as pattern matching, succinct data structures and external memory algorithms, for which nearly-optimal solutions are possible. We will discuss a variety of techniques for different problems and different computational models.
Second are problems, such as network optimisation, where sometimes only exponential-time algorithms are known. We will discuss when these problems admit exact efficient solutions, and when only approximation is possible. Some key tools will be randomness and linear programming
Aims: To provide the student with a deep understanding of the most important recent advances in algorithms and data structures and the tools needed to analyse them. This unit should be of particular relevance to anyone with a strong interest in the mathematical aspects of computer science.
S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani. Algorithms McGraw-Hill, 2006. ISBN: 0-073-52340-2 Background
Cormen, Leiserson, Rivest, Stein Introduction to Algorithms (3rd Edition) MIT Press ISBN: 978-0262533058 Background
