CS3 Algorithms and Data Structures
This module runs in term 1, with lectures on
Tuesdays at 10:00
Joseph Black Th 250
Thursdays at 11:00
JCMB Th A
of this module can be viewed through the
CS3 Course Guide
will be allocated at the beginning of the second week of term 1.
Overview of the course.
O() notation and recurrences (review of CS2); Strassen's algorithm for matrix multiplication.
Solving recurrences (review of CS2).
Fast Fourier Transform (FFT).
Motivation for and applications of the FFT.
Finding the median.
The disjoint sets data structure: specification and applications.
The disjoint sets data structure: implementation.
Introduction to dynamic programming: Matrix-chain multiplication
Dynamic programming continued: Longest common subsequences
Maximum flow, Ford-Fulkerson algorithm
Introduction to computational geometry
Detecting intersections of line segments
Finding the convex hull
There are three assessed exercise sheets, with submission deadlines in weeks 4, 7 and 10. They account for 30%, 40% and 30%, respectively, of the cousework component.
Exercise Sheet 1 (deadline Friday 1st November)
Exercise Sheet 2 (deadline Friday 22nd November)
Exercise Sheet 3 (deadline Wednesday 11th December).
Past Examination Papers
Martin Grohe, email@example.com, JCMB room 1605, ext. 505135