Algorithmics

Short Description
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.
Timetable
Two one-hour lectures and one one-hour tutorial per week.

Course Aims
- 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.

Intended Learning Outcomes of Course
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. Demonstrate an understanding of the concepts of balanced trees and digital trees, and the algorithms for manipulating these structures;
4. Code standard efficient sorting algorithms;
5. Code fundamental graph algorithms - for search and traversal, shortest paths, minimum spanning trees, and topological sorting;
6. Describe classical algorithms for string searching, string comparison, and text compression;
7. Expound on the basic principles, and the practical implications of, the theory of NP-completeness;
8. Follow NP-completeness proofs for particular problems;
9. Deploy various strategies for dealing with computational problems that are apparently intractable;
10. Provide examples of the computability and unsolvability, and know some standard examples of unsolvable problems.