next up previous

CSE 5311 Fall 1999

Quiz #12

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

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

\begin{displaymath}\{(x_1, y_1), \; (x_2, y_2), \; \ldots \; (x_n, y_n)\},\end{displaymath}

such that \(y_i \; < \; y_{i+1}\), which two points are guaranteed to be included in a convex hull? Justify your answer.