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 ________ _________ ________ ________ _______ ______.
_____ ____ ___ _______ _________ _____ ____ ______ _________ ________ ______ ___.
____ __________ __________ _____ ________ __________ _______ ______.
__________ __________ __________ ___ ________ ____ ______ _______ ___ ______ _________ ___.
___ _______ ____ ____ ___.
__________ ______ _________ _________ __________ ______ ____ ___ _________ ________.
_______ _________ ________ __________ ____ _________ _______ ___ _____ ______ _____.
__________ _____ ___ ___ ________ ________.
__________ __________ _______ ________ ________ ________ _________ _____ _______ ________ ________.
___ ____ _________ ____ ____ _________.
__________ ______ ____ ___ _____ ____.
__________ ____ ____ ____ ____ _______ ___ ________ _________ _________.
______ __________ ______ ___ _________ _______.
_________ ______ _____ _______ __________ __________ _________.
_____ ________ _________ _________ _______.
_______ _____ ____ _______ ____ ______ _________ __________ _______ ____ _______.
_____ _________ _____ ___ _________ ____ __________ ____ _______ __________.
______ _______ __________ _______ ______ _____ ___ ______ ___ __________ ___ ______.
______ ________ ____ ________ _________ _____ ____ ___ __________ ___.
_________ ________ _________ ________ ___ _______ ____ ___ ___ _______ _______ _____.
________ ___ ______ ______ ________ ________.
_____ ________ __________ _________ ___ ___ ______ _____ _______ _____.
_______ _____ ______ _________ __________ ____.
_____ _______ __________ _________ _____ _______ __________ ____ _______ _______.
_________ ___ _________ _______ ___ _________ _______.
_____ _____ __________ _________ ____ _________ _____ ________ __________ ______.
_____ ___ ______.
Get Full Answer on WhatsApp
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 .
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).
Use Kruskal's algorithm to find a minimal spanning tree in the graph given below
Construct a binary search tree with the following keys, inserting them in the given order:
110, 8, 19, 6, 9, 12, 32.
Apply DFS algorithm to find a spanning tree of the following graph. Also find all the fundamental cycles of the spanning tree.
With the help of an example, explain the following:
i) Algorithm,
ii) Input and output for an algorithm
iii) Running time of an algorithm (5)
b) Illustrate the operations of partition in quick sort on the array
.
Taking v1 as the root, find a spanning tree of the following graph using the breadth first search (BFS) algorithm.
