[Note: based on 1990-91 course description, D.R.W.]
Lecturer: Colm Ó Dúnlaing
Date: 1995-96
Groups: Optional JS and SS Mathematics, SS Two-subjecct Moderatorship
Prerequisites: There are no formal prerequisites. Students with little experience of data structures - lists, stacks, queues, trees, and so on - would not be advised to take this course. The course will not involve any programming.
Duration: 21 weeks
Lectures per week: 3
Assessment: Homeworks counted.
Examinations: One 3-hour examination
Some or all of the following material will be covered as time permits. Sorting: mergesort, heapsort, quicksort, radix sort - worst-case and average analysis. Lower bound for sorting in comparison model. Searching: average-case analysis of binary search-trees, worst-case for red/black trees, amortised analysis of splay trees. Hash addressing: analysis of uniform rehashing and linear resolution. Perfect hashing. Enumeration of binary trees; average depth of a binary tree.
Amortised analysis of the UNION-FIND strategies. String matching: KMP. Digraphs and graphs. Depth-first search. Topological sort. Strong connectivity. Biconnectivity. Dijkstra's algorithm. LR(1) parsers. Finite automata. Graph planarity. Bipartite marching. Network flows.
Objectives: This course aims to cover a rather wide range of algorithms and analyse their efficiency.