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

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.