Module MA3467: Algorithms
Credit weighting (ECTS)
Michaelmas term 2013-14
11 weeks, 3 lectures including tutorials per week
Teaching Lectures will be delivered on blackboard, with notes posted regularly on the Internet.
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.
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.
Boyer-Moore algorithm (if time permits).
The union-find problem.
Directied graphs: depth-first search, acyclicity, strong connectivity.
Tarjan's strong components algorithy.
Module Prerequisite None
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.