next up previous contents
Next: Compiling Techniques Up: Descriptions of Modules and Previous: Major Projects   Contents

Subsections

Algorithms and Data Structures

Description

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.

Syllabus

The syllabus below is provisional; deviations may occur and will be documented in the Lecture Log for the module.

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.

Assessed Coursework

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.


\begin{references}
\par\stars{3} T.H. Cormen, C.E. Leiserson and R.L. Rivest \em...
...ar\stars{1} R. Sedgewick \emph{Algorithms}, Addison-Wesley.
\par\end{references}


next up previous contents
Next: Compiling Techniques Up: Descriptions of Modules and Previous: Major Projects   Contents
CS3 dummy user 2001-09-25