Algorithms and Data Structures

Here are links to the course home page and the formal TQA description.

Description

The course aims to provide general techniques for the design of efficient algorithms and, in parallel, develop appropriate mathematical tools for analysing their performance. In this, it broadens and deepens the study of algorithms and data structures initiated in CS2. Along the way, problem solving skills are exercised and developed.

Syllabus

Introductory concepts

Review of CS2. Models of computation; time and space complexity; upper and lower bounds, big-O and big-Omega notation; average and worst case analysis.

Divide and conquer

Matrix multiplication: Strassen's algorithm; the discrete Fourier transform (DFT), the fast Fourier transform (FFT). Expressing the runtime of a recursive algorithm as a recurrence relation; solving recurrence relations.

Sorting and selection

Quicksort and its analysis; selection in expected linear time.

Data structures: Disjoint sets

The ``disjoint sets'' (union-find) abstract data type: specification and implementations as lists and trees. Union-by-rank, path-compression, etc., ``heuristics''. Applications to finding Minimum Spanning Trees.

Dynamic programming

Introduction to the technique; application to Matrix-chain multiplication.

Graph/Network algorithms

Network flow, Max-flow/min-cut theorem, Ford-Fulkerson algorithm.

Geometric algorithms

Intersecting line segments in two dimensions; convex hull of a set of 2-D points (Graham's scan algorithm).

Assessed Coursework

There will be three assignments designed to aid students' understanding of the lecture material. At least two of these will be pencil and paper exercises. One of them may be a programming exercise.

References:

*** Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition). MIT Press, 2002.

* Gibbons: Algorithmic Graph Theory. Cambridge University Press, 1985.

* Goodrich, Tamassia: Algorithm Design - Foundations, Analysis, and Internet Examples. Wiley, 2002.