To develop the student's skills in the design and analysis of algorithms; To study algorithms for a range of important standard problems; To introduce the student to the theory of NP-completeness together with its practical implications;To make the student aware of fundamental concepts of computability.

Two one-hour lectures and one one-hour tutorial per week.

None

None

Examination 75%, assessed practical exercise 20% and in-class quizzes 5%.

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 coursework cannot be redone because the nature of the coursework is such that it takes a significant number of days to produce it and this effort is infeasible for supporting the re-doing of such coursework over the summer.

To develop the student's skills in the design and analysis of algorithms;

To study algorithms for a range of important standard problems;

To introduce the student to the theory of NP-completeness together with its practical implications;

To make the student aware of fundamental concepts of computability.

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

1. Recognise, and be able to use, standard algorithmic design methods;

2. Apply the basic principles of algorithm analysis;

3. Code standard efficient sorting algorithms;

4. Code fundamental graph algorithms - for search and traversal, shortest paths, minimum spanning trees, and topological sorting;

5. Describe classical algorithms for string searching, string comparison, and text compression;

6. Expound on the basic principles, and the practical implications of, the theory of NP-completeness;

7. Follow NP-completeness proofs for particular problems;

8. Deploy various strategies for dealing with computational problems that are apparently intractable;

9. Provide examples of the computability and unsolvability, and know some standard examples of unsolvable problems.

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