Formal module description

Formal module syllabus

The module organiser is Alexander Tiskin.

Revision lectures:

• Friday 5 May 12:00, room CS104
• Tuesday 9 May 15:00, room CS104
• Friday 12 May 10:00, room CS104
• NEW: Monday 15 May 12:00, room CS104

Lecture slides (subject to occasional updates/corrections, last updated 11/4/17):

• presentation format
• printing format [4 per page]

Lecture notes on the Discrete Fourier Transform: pdf

2017 examinable material by chapter, titles of examinable sections in parentheses:

1. Computation by circuits (all sections)
2. Parallel computation models (The PRAM model, The BSP model, standard communication patterns)
3. Basic parallel algorithms (all sections)
4. Further parallel algorithms (sorting, selection [except accelerated regular sampling], convex hull [except 3D regular sampling])
5. Parallel matrix algorithms (matrix-vector multiplication, matrix multiplication [except communication lower bound]).
6. Parallel graph algorithms: this chapter is not examinable

Coursework (please attach an appropriate cover sheet and submit into a collection box in CS0.06)

• Assignment 0: self-study, not for credit. To be discussed in seminars.
• Assignment 1: counts as 10% of the module credit. Due on 9/2/17 (Thursday week 5) at 12noon. Solutions
• Assignment 2: counts as 10% of the module credit. Due on 9/3/17 (Thursday week 9) at 12noon. Solutions

All the lecture material is covered by the set of slides above. Much of this material is not (yet) present in any textbooks: the nature of this module is to teach “advanced topics”, some of which may stem from recent research. Therefore, the lectures, seminars and revision classes should be taken extra seriously.

Some (by no means all) topics are covered by the following books:

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 2nd edition, The MIT Press, 2001. In particular, Chapter 27 on Sorting Networks (note: this chapter has been dropped from the 3rd edition). Available via Warwick Library
• Al-Haj Baddar and Batcher, Designing sorting networks: a new paradigm, Springer, 2013. Free e-book available via Warwick Library.
• Bisseling, Parallel Scientific Computation: A Structured Approach using BSP and MPI, Oxford University Press, 2004. Free web-formatted e-book available via Warwick Library.

Some material can also be found in the following books (however, the presentation format and emphasis will typically differ from this module):

• Gibbons and Spirakis (eds), Lectures on Parallel Computation, Cambridge University Press, 1993.
• JaJa, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
• Gibbons and Rytter, Efficient Parallel Algorithms, Cambridge University Press, 1988.
• Leighton, Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes, Morgan Kaufmann, 1992.

Module forum

Exam questions will include both bookwork (i.e. restating the concepts and proofs as given in the lectures) and application (i.e. applying this knowledge in problem solving). All the examinable material will have been given in the lectures. Past exam papers (available with Warwick login): 2014, 2015, 2016.