C++代写 | Data Structure & Algorithm Assignment 5

C++代写 | Data Structure & Algorithm Assignment 5

Problem 1

a) Draw the kd-tree corresponding to the set of points:
S = {p1,…,p8} = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8)}.

b) Construct a kd-tree storing n = 4 two dimensional points in general position s.t. there
exists a range search returning an empty result and yet all nodes of the kd-tree are
explored. Draw the picture with the points, the splits of the kd-tree and the rectangle
R representing the range search.

c) Can the result in (b) be generalized to arbitrary large values of n?

d) Suppose set S contains 2D points with integer coordinates, but these points are not
necessarily in general position, namely two distinct points can have either the same x
or the same y coordinate (but not both, i.e. all points in S are distinct). Therefore
the standard kd-building algorithm on S does not guarantee a balanced tree.
Explain how to modify the points in S to build a new set of points S0
,wherepoints
in S0 are in general position, and any range search on S can be transformed into an
equivalent range search on S0
.Coordinatesin S0
do not have to be integers. Explain how to convert a range search on S into an equivalent
range search on S0
. Note that
when range-searching in S,thequeryboundariesarenotnecessarilydeﬁnedbyintegers.

Problem 2

a) Draw a range tree that corresponds to the following set of 2D points:
S = {(3, 4), (10, 2), (9, 9), (5, 7), (6, 1), (0, 3), (1, 8)}.
Draw the primary tree, and then all the auxiliary trees. Make the primary tree and
all the auxiliary trees of the smallest height possible. Make sure to indicate to which
node v an auxiliary tree T(v) belongs to.

b) Explain how to construct a two dimensional range tree containing n points in O(n log n)
time. Brieﬂy justify your time complexity.

Problem 3

for, and h(k)= k mod M.Giveatext T,withlength9thatproducestheworst-casenumber
of comparisons for Rabin-Karp ﬁngerprinting. T should not contain pattern P.Explainwhy
T produces the worst-case.

Problem 4

a) Compute the KMP failure array for the pattern P = bbbabb.

b) Show how to search for pattern P = bbbabb in the text T = bbbcbbacbbbbbabb using
the KMP algorithm. Indicate in a table such as Table 1 which characters of P were
compared with which characters of T, like the example in Module 9. Place each
character of P in the column of the compared-to character of T.Putroundbrackets
around characters if an actual comparison was not performed. You may need to add
extra rows to the table.

c) Given two words w and v,eachoflength n,explainhowtousetheKMPalgorithm
to ﬁnd if one string is a cyclic shift of another in O(n)time. Forexample, alloy is a
cyclic shift of loyal but alloy is not a cyclic shift of aloyl.