The aims of the course are:

To present a broad range of algorithm design methods, with examples chosen to reflect practical applications;

To enable students to make educated choices between strategies for algorithmic problem-solving;

To convey the significance of computational complexity, and to present a range of methods for dealing with it in practice.

3 hours per week

None 

None 

Examination 70%, In-class quizzes 10%, Assessed practical exercise 20%.

The aims of the course are:

To present a broad range of algorithm design methods, with examples chosen to reflect practical applications; to enable students to make educated choices between strategies for algorithmic problem-solving; to convey the significance of computational complexity, and to present a range of methods for dealing with it in practice.

By the end of the course students will be able to:

1. Describe a wide range of efficient algorithms for problems with important applications in domains such as computational geometry, string processing and graph theory;

2. Discuss why these algorithms are correct, and prove their correctness;

3. Demonstrate the execution of such algorithms as applied to typical problem instances;

4. Characterise and manipulate advanced data structures such as the suffix tree;

5. Apply algorithmic techniques to specific problems motivated by practical applications;

6. Analyse the worst-case complexity of algorithms using a variety of mathematical techniques;

7. Discuss the theory and practical implications of NP-completeness;

8. Explain techniques for coping with complexity, such as backtracking algorithms, pseudo-polynomial-time algorithms, constant-factor approximation algorithms, and polynomial-time approximation schemes;

9. Construct proofs of NP-completeness and inapproximability results.