The CS3 *Algorithms and Data Structures* course is concerned with the
application of (mostly elementary) mathematical techniques to the design and
analysis of efficient algorithms. The range of techniques for algorithm design
introduced in the first and second year courses is augmented and developed.
The notion of computational complexity is stressed as an integral part of the
problem solving process.

**Introductory Concepts**- Models of computation; time and space
complexity; upper and lower bounds; average and worst case analysis.
**Algebraic Algorithms**- Matrix multiplication: Strassen's algorithm;
polynomial arithmetic: the fast Fourier transform.
**Sorting and Selection**- Quicksort and its analysis; selection
in linear time.
**Advanced Data Structures**- Hashing; data structures for the union-find
problem; 2-3 trees.
**Graph Algorithms**- Network flow and bipartite matching.
**Geometric Algorithms**- Intersecting line segments in two dimensions;
convex hull of a set of points (in 2-d).
**Approximation Algorithms for Hard Problems**- Intractability: necessity for approximations; some examples.

There will be three assignments designed to aid students' understanding of the lecture material. These will consist largely of pencil and paper exercises, but there may also be some small programming tasks.