Pattern Matching Algorithms

    Syllabus

    Reading Material

    See also "Jewels in Stringology" by Crochemore and Rytter, chapter 15.

    Course Scribe Notes

    Transparencies

  1. KMP
  2. Witness Table Pattern Matching Algorithm
  3. The Dueling Algorithm
  4. Renaming
  5. Deterministic Sampling
  6. The Convolutions Method
  7. Fastest-known k-Mismatches Matching
  8. Parameterized Matching (PPT)
  9. Parameterized Matching with don't cares
  10. 1-d Scaled Matching (PPT)
  11. Indexing Problem
  12. Weiner's Suffix Tree Construction Algorithm
  13. Berkman's LCA Algorithm
  14. Maximum Agreement Homeomorphic Trees Algorithm
  15. Bandelt and Dress Theorem
  16. A Bird's Eye View - 2d Matching (PPT)
  17. Rotation
  18. Interchange Matching (PPT)
  19. Interchange Matching - Address Errors (PPT)
  20. Pattern Matching Algorithms - test 1999 (pdf)
  21. Pattern Matching Algorithms - test 2010 with solutions (pdf)

    Exams

  1. moed alef 2015.
  2. moed bet 2015.


Back to Amihood Amir's homepage.