Description
1. Construct the Longest Common Subsequence (LCS) matrix
comparing the strings “aaabcaadaabaaa” and “abcdba”.
What is the LCS?
2. Draw a figure illustrating the comparisons done by the
brute-force pattern matching algorithm for the text
“aaabcaadaabaaa” and pattern “aabaaa”. Determine the
number of comparisons needed.
3. Draw a figure illustrating the comparisons done by the
Boyer-Moore (BM) matching algorithm for the text
“aaabcaadaabaaa” and pattern “aabaaa”. Determine the
number of comparisons needed.
4. Draw a figure illustrating the comparisons done by the
Knuth-Morris-Pratt (KMP) matching algorithm for the text
“aaabcaadaabaaa” and pattern “aabaaa”. Determine the
number of comparisons needed.
Due April 29th
