For the following set of points, describe how the CLOSET-PAIR algorithm finds a closest pair of points:
(1,2),(2,−1),(3,−3),(3,2),(−3,4),(−1,2),(2,3),(1,1),(−5,−2).
The nine points are first sorted by x-coordinate: ((-5,-2),(-3,4),(-1,2),(1,1),(1,2),(2,-1),(2,3),(3,-3),(3,2)). The median x-value is between ((1,2)) and ((2,-1)), so the set is divided into a left half (L={(-5,-2),(-3,4),(-1,2),(1,1),(1,2)}) and a right half (R={(2,-1),(2,3),(3,-3),(3,2)}). In the left half, sort by x again and split around the median between ((-1,2)) and ((1,1)). (L_1={(-5,-2),(-3,4),(-1,2)}) and (L_2={(1,1),(1,2)}). In (L_1) all pairs are checked: distance between ((-5,-2)) and ((-3,4)) is (\sqrt{(2)^2+(6)^2}=\sqrt{40}), between ((-5,-2)) and ________ ___ ___ _____ _________ ____ ____.
____ _____ __________ _________ _____ ____ _____ _______ ______.
______ _______ ______ ___ ___ _________ ________.
______ _________ _________ ______ _______.
_________ _____ _____ ________ ___ ________.
___ _______ __________ _________ __________ _________ ___ ___ _____.
_____ ______ _____ ________ _____ _______ _________ _____ __________ ____ ____ __________.
_____ __________ ______ ____ _____ ________ ______ ___.
__________ ____ ______ _______ ________ _______.
____ __________ _________ _________ __________ _________ _________ ____ _________ _______ __________ _______.
___ _________ ___ __________ ________ ______ __________ ______ ________.
______ ___ _________ _________ ______ ________ __________ ______ ___ ______.
____ ___ _________ __________ ________ _____ _____.
________ ____ ______ _____ _____ _________ ______ ______ ________ ______.
_____ __________ __________ _________ _____ ______.
________ __________ ____ ____ _______ _________ ______ ___ _________ _________ _____.
________ ______ _______ ___ _______ ________ ___ _____ ________ ________ _________ _____.
___ __________ ___ _________ ___ _______ ________ _________.
_____ _______ ____ _____ ______ ____ ________ _____.
____ ___ _______ ___ _____.
________ ____ __________ ____ _________ __________ __________.
___ _______ ________ ______ _______ _______ _______ ______ ______ ___.
________ ________ ____ ________ _____ ___.
__________ ________ _________ ___ ________ ___ ________ _____ ____ ________.
______ _________ _____ _________ _______.
Get Full Answer on WhatsApp
Construct a binary search tree with the following keys, inserting them in the given order:
110, 8, 19, 6, 9, 12, 32.
Find an optimal parenthesisation of a matrix chain product whose sequence of dimensions is (4,8,7,2,3).
Show the results of inserting the keys
C, R, A, U, J, S, F, T, O, P, M, L, N, W, Q
in order into an empty B-tree with minimum degree 2. Only draw the configurations of the tree just before some node must split, and also draw the final configuration.
Apply DFS algorithm to find a spanning tree of the following graph. Also find all the fundamental cycles of the spanning tree.
Show step by step how you will construct a binary search tree by inserting keys in the order 12, 6, 4, 7, 8, 10, 7, 5, 13, 16, 11, starting from an empty binary tree. Explain step by step how you will delete the node with the key 13 from the binary tree. (5)
b) Illustrate the operations of performing counter sort on the array .
Construct a MAXHEAP tree on the following list of numbers
15, 22, 7, 10, 43, 52 13, 16,
Determine an LCS of (1, 1, 1, 1, 0, 1, 1, 0, 1, 0) and (1, 1, 1, 0, 0, 1, 1, 0, 1, 0).