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''?

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?

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.