Trinity College Dublin

Skip to main content.

Top Level TCD Links

Sitemap

Module MA346M: Topics in Advanced Programming

Credit weighting (ECTS)
5 credits
Semester/term taught
Michaelmas Term 2017/18
Contact Hours
11 weeks, 3 lectures including tutorials per week
 
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.

Topics
 
  • 'Bags' Insert, delete, and search.
  • Heaps and heapsort.
  • Linked lists.
  • Binary trees, binary search trees; find, insert, delete, join, split.
  • Red-black trees.
  • Splay trees.
  • Union/Find.
  • Hash coding.
  • Bloom filters.
  • String matching (if time permits).
  • Tries and string matching (if time permits).
  • Directed graphs.
  • Topological sort.
  • Strong components: Sharir and Tarjan.
  • Shortest weighted paths: Floyd-Warshall and Dijkstra.
Assessment Detail
Fortnightly in-class quizzes for 10%, programming assignments for 20% and 70% for the final 2-hour exam in May. Supplementals if required will consist of 100% exam.
Prerequisites
MA1262, MA1264
Teaching
Lectures will be delivered on blackboard, with notes posted regularly on the Internet.