Skip to main content

CS341 Advanced Topics in Algorithms (will not be taught from 17/18)

Academic Aims

To introduce students to new techniques, methods and results from the rapidly-developing field of algorithms. Typical topics include randomised algorithms, graph algorithms, matrix algorithms and counting algorithms. The module will be research-led, so exact topics will vary from year to year.

Learning Outcomes

Students will be able to understand a variety of advanced algorithmic techniques, use recently-developed algorithmic techniques to solve problems, and understand the state of the art in some areas of algorithmic research, including new developments and open problems.


  • Basic parallel computation models: circuits, comparison networks. Parallel merging and sorting by comparison networks.
  • Advanced parallel computation models: PRAM, BSP.
  • Fundamental parallel algorithms: total exchange, broadcast/combine, prefix sums, butterfly, grid.
  • Further parallel algorithms: list and tree contraction, sorting, convex hull
  • Parallel matrix algorithms: matrix-vector multiplication, matrix multiplication, triangular system solution, Gaussian elimination.
  • Parallel graph algorithms: algebraic paths, all-pairs shortest paths, minimum spanning tree.

Content in previous years.

  • Sorting, selection, etc.
  • Search trees, skip lists.
  • Cuts, flows, approximation algorithms for graph problems.
  • Online algorithms.

15 CATS (7.5 ECTS)
Term 2

Alex Tiskin


Online material