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.