Course Catalogue

View Specification Document | Reading List

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

Algorithmics I (H) (or equivalent)

None 

None 

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

Reassessments are normally available for all courses, except those which contribute to the Honours classification. For non Honours courses, students are offered reassessment in all or any of the components of assessment if the satisfactory (threshold) grade for the overall course is not achieved at the first attempt. This is normally grade D3 for undergraduate students and grade C3 for postgraduate students. Exceptionally it may not be possible to offer reassessment of some coursework items, in which case the mark achieved at the first attempt will be counted towards the final course grade. Any such exceptions for this course are described below. 

The assessed practical exercise cannot be redone because the nature of the coursework is such that it would take a significant number of days to produce it and this effort is infeasible for supporting the re-doing of such coursework over the summer.  The assessed quizzes cannot be redone as they are intended to be answered in class only.

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.

Students must submit at least 75% by weight of the components (including examinations) of the course's summative assessment.