Module MA3467: Algorithms

Credit weighting (ECTS)

5 credits

Semester/term taught

Michaelmas term 2013-14

Contact Hours

11 weeks, 3 lectures including tutorials per week

Teaching

Lectures will be delivered on blackboard, with notes posted regularly on the Internet.

Lecturer

Prof. Colm Ó Dúnlaing

Learning Outcomes

On successful completion of this module, students will be able to

• Estimate the runtime of various algorithms.
• Recognise where certain algorithms are applicable, and where they are unsuitable.
• Extend their knowledge of algorithms or proceed to applications or to further study of the subject.

Module Content

• Binary search, trees, binary trees, enumeration, binary search trees, average cost of searching, Hibbard's deletion strategy. Enumberation trees of given path-lenth.
• Red-black trees, splay trees, heaps, heapsort, mergesort, bucket sort, quicksort.
• Knuth-Morris-Pratt algorithm.
• Boyer-Moore algorithm (if time permits).
• The union-find problem.
• Directied graphs: depth-first search, acyclicity, strong connectivity.
• Tarjan's strong components algorithy.
• Hash tables.
• Bloom filters.

Module Prerequisite

None

Assessment Detail

This module will be examined in a 2-hour examination in Trinity term. Fortnightly written assignments will account for 10% of the final annual mark. Supplemental exam, if required will consist of 100% exam.