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%.

It is the default expectation that all courses will offer opportunities for reassessment or deferred assessment. Where it is not possible to offer this in some assessment components, the grade achieved at the first attempt will be counted towards the final course grade, and any exceptions for this course are described below.

[No exceptions]

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.