Show/hide main menu

Modules

6CCS3PAL Parallel Algorithms

Credit value: 15

Lecturer: Professor Colin Cooper (office hours)
Semester: 1
Teaching pattern: weekly 3-hour lecture
Assessment: 100% written examination, 2 hours (Marking Model 2 - Double Marking)

Learning aims & outcomes
To introduce classical results on parallel algorithmic design and to illustrate how they may be cleanly, concisely and efficiently expressed using the nested data-parallel paradigm.

This module introduces the design principles and analysis techniques for parallel algorithms. On successful completion of this module you will understand the creation of efficient parallel algorithms in a range of application areas, including sorting, matrix and graph based problems.

Syllabus
Models of Parallel Computation:
  • Typical parallel models
  • Complexity measures
Designing Parallel Algorithms:
  • Basic PRAM techniques
  • Doubling Technique
  • Summation trees and prefix summation
Interconnection networks:
  • Graph models of networks
  • Network properties
  • Searching and sorting on meshes
Sorting and Searching on PRAMs:
  • Merge sort
  • Compare-exchange sorts
  • Batcher's sorting algorithms
  • Computing the Median
Pointer-based algorithms:
  • List ranking
  • Tree contraction
  • Connected components
  • Minimum spanning tree
  • All-pairs shortest path
Geometric Algorithms:
  • Convex hulls
  • Closest pair of points
  • Visibility
Distributed methods:
  • Search and network construction
Suggested reading/resources

07 September 2017
Sitemap Site help Terms and conditions  Privacy policy  Accessibility  Modern slavery statement  Contact us

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454