CS3 Algorithms and Data Structures

• The syllabus of this module can be viewed through the CS3 Course Guide

• Tutorial groups will be allocated at the beginning of the second week of term 1.

• Lecture Log

• Lectures Slides and Notes
  • Lecture 1. Overview of the course.
  • Lecture 2. O() notation and recurrences (review of CS2); Strassen's algorithm for matrix multiplication.
  • Lecture 3. Solving recurrences (review of CS2).
  • Lecture 4. Fast Fourier Transform (FFT).
  • Lecture 5. Motivation for and applications of the FFT.
  • Lecture 6. Quicksort.
  • Lecture 7. Order statistics.
  • Lecture 8. Finding the median.
  • Lecture 9. The disjoint sets data structure: specification and applications.
  • Lecture 10. The disjoint sets data structure: implementation.
  • Lecture 11. Introduction to dynamic programming: Matrix-chain multiplication.
  • Lecture 12. Dynamic programming continued: Longest common subsequences.
  • Lecture 13. Flow networks.
  • Lecture 14. Maximum flow, Ford-Fulkerson algorithm.
  • Lecture 15. Introduction to computational geometry.
  • Lecture 16. Detecting intersections of line segments.
  • Lecture 17. Finding the convex hull.

• Coursework
  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
  • June 1992
  • June 1993
  • June 1994
  • June 1995
  • June 1997
  • June 1999
  • May 2000
  • June 2001
  • June 2002