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,

$$\{(x_1, y_1), \; (x_2, y_2), \; \ldots \; (x_n, y_n)\},$$

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.