Skip to main content

Trinity College Dublin, The University of Dublin

Trinity Menu Trinity Search

School of Mathematics

You are here Courses > Undergraduate > Courses & Modules

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.