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, 21:16): §5.1 Elementary parallel string matching
  
  Chapters

  1:18 Parallel string matching
  4:33 Elementary parallelization
  9:07 Subproblems
  12:45 Solution
  19:34 Wrapup
  
• Video 5-2 (2022-03-07, 15:21): §5.2 Periodicity
  
  Chapters

  0:20 Periodicity of Strings
  9:59 Periodic strings
  14:14 Clicker Question
  
• Video 5-3 (2022-03-07, 22:30): §5.3 String matching with duels
  
  Chapters

  0:23 Periods and Matching
  4:50 Dueling example
  13:13 String Matching by Duels - Sequential
  16:05 String Matching by Duels - Parallel
  19:26 Computing witnesses
  20:05 Parallel Matching - State of the art
  

---

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