Z algorithm and KMP algorithm - Lesson plan

Learning outcomes

• able to evaluate performance of matching algorithms in terms of number of comparisons
• understand how pre-computing exact matches helps matching
• able to compute Z values
• understand why Z value computation is linear time
• able to understand why precomputed sp values help speed up alignment
• able to compute sp' values from Z values
• able to compute sp values using traditional KMP approach

Class plan

• Q/A based on reading
• make sure concept of Z values is understood
• run through algorithm for computing Z values
• make sure concept of sp values is understood
• computation of sp values from Z values
• why is KMP fast?
• run through: http://whocouldthat.be/visualizing-string-matching/ Links to an external site.
• traditional computation of sp values

Exercises

Rosalind KMP

Rosalind SUBS - compare speed with Rosalind 1C from previous submission

 Exercises from handout

Additional resources

https://youtu.be/CpZh4eF8QBw Links to an external site.

https://ivanyu.me/blog/2013/10/15/z-algorithm Links to an external site.

https://www.youtube.com/watch?v=rfisBOOLN9M Links to an external site. Links to an external site.

https://www.utdallas.edu/~besp/demo/John2010/z-match.htm Links to an external site.