Module Summary:

Aims of this Module:
To describe a number of advanced topics in the design and analysis of efficient sequential algorithms, and a few key results related to the study of their complexity. At the conclusion of the module students should:

• 1. Understand the role of algorithmics within Computer Science.


• 2. Have expanded their knowledge of computational complexity theory.


• 3. Be aware of current research-level concerns in the field of algorithm design.

Teaching and learning strategies:
Students will be expected to attend three hours of formal lectures in a typical week. Lectures will introduce students to the academic content. In addition, students will be expected to devote unsupervised time to private study. Private study will provide time for reflection and consideration of lecture material and background reading. For each unit of this module, practical applications of the techniques students learn will be explored and demonstrated.

Syllabus Outline:

Algorithmic paradigms: greedy algorithms with applications to scheduling. Dynamic programming with applications to matrix-chain multiplication and the longest-common subsequence problem.

Pattern-matching algorithms including FSA and the Knuth-Morris-Pratt algorithm.

Lossless compession algorithms including Huffman coding.

Graph algorithms for finding maximum matchings in bipartite graphs and trees.

NP-Completeness including the status of the P v NP problem and polynomial-time reductions for some classic problems.

Approximation Algorithms the complexity class NPO and methods for designing efficient approximation algorithms. Also, the complexity classes APX and PTAS.

Plus selected further topics.