Unit 5: Parallel String Matching

This is an archived version of this module from Spring 2022.
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

1. Know and apply parallelization strategies for embarrassingly parallel problems.
2. Identify limits of parallel speedups.
3. Understand string matching by duels, both sequential and parallel (excluding preprocessing).

Material

• slides

• lecture notes

• Video 5-1 (2022-03-07): §5.1 Elementary parallel string matching

• Video 5-2 (2022-03-07): §5.2 Periodicity

• Video 5-3 (2022-03-07): §5.3 String matching with duels

---

Further reading and sources

The presentation of sequential and parallel matching by duels takes inspiration from:

• Crochemore, Rytter: Jewels of Stringology (2002), World Scientific

---

Unit 4  ⋅  Syllabus  ⋅  Unit 6