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

CS341 15 CATS (7.5 ECTS) Term 2

## Availability

Core - DM. Option - CS and CSys

## Prerequisites

CS260 Algorithms

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.

## Content

• 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.

## Books

• Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein; in particular, Chapter 27 on Sorting Networks.
• Parallel Scientific Computation: A Structured Approach using BSP and MPI by Rob Bisseling. The official book website includes a freely downloadable introduction chapter, which gives a detailed description the BSP model.

## Assessment

Three-hour examination (80%), coursework (20%)

## Teaching

30 one-hour lectures, 4 Seminars