Course 363 - Algorithms and complexity

[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.