CSE 5311 Fall 1999

**Quiz #12**

- 1.
- (15 points.)
What good suffix values and bad character values would be computed using
the Boyer Moore algorithm for the pattern P = ``panama canal pan''?
Good Suffix Values 16 - max 0<=k<16 | P[j+1..m] suffix of P_k or P_k suffix of P[j+1..m] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 13 13 13 13 13 13 13 13 13 13 13 13 13 13 6 6 1 Bad Character Values a c l m n p 15 8 12 5 16 14

If a mismatch occurs at position j = 14 in the pattern array, where the mismatched character in T is ``n'', how far over will the window be moved?

s = s + max(gs[j], j - bc[n]) = s + max(6, 14-16) The window will be moved over 6 positions.

- 2.
- (5 points.)
Given points ordered by strictly increasing
*y*values,

such that , which two points are guaranteed to be included in a convex hull? Justify your answer.The points with the smallest and largest y coordinate values would be included in the convex hull. These points are specifically included by the Jarvis' March algorithm. The points with the smallest and largest x coordinate values would also be included in the convex hull.