main page — COMP 526 Applied Algorithmics
Unit 5: Parallel String Matching
This is an archived version of this module from Spring 2020.
Click here for the current iteration.
This unit covers some algorithms for exact string matching on parallel computers:
- exploiting embarrassingly parallel problems
- sequential matching by duels
- parallel matching my duels
Learning outcomes
- Know and apply parallelization strategies for embarrassingly parallel problems.
- Identify limits of parallel speedups.
- Understand string matching by duels, both sequential and parallel (excluding preprocessing).
Material
- lecture notes
- slides
- tutorial problems
- Lecture 2020-03-03: Embarassingly parallel approaches, periodicity
- Lecture 2020-03-03: Matching by duels
Further reading and sources
The presentation of sequential and parallel matching by duels takes inspiration from: