Question & Answer: Using Python, please answer all the questions:)…..

Given in points in the plane, consider the problem of finding the pair of points that is closest together. One algorithm for doing this is the brute-force method: list all the pairs, compute their distances, and take the smallest one. (i) Explain how this brute-force algorithm can be implemented without ever computing a square root. (ii) Implement this algorithm in Python (without using square roots). Your code should accept a list of points (ordered pairs () of floats) and return the two points that are closest together (iii) Show that this algorithm has temporal complexity in o(nº) (where the fundamental operations include basic arithmetic operations +,-, X, I, assigning a value to a variable or to a given position in a list, looking up the value of a particular element at a given position in a list, comparing two values, and incrementing a value ). Surprisingly, there is a on logn) algorithm for solving this problem (see (KTO5, $5.4).

Using Python, please answer all the questions:)

Given in points in the plane, consider the problem of finding the pair of points that is closest together. One algorithm for doing this is the brute-force method: list all the pairs, compute their distances, and take the smallest one. (i) Explain how this brute-force algorithm can be implemented without ever computing a squareroot . (ii) Implement this algorithm in Python (without using squareroot s). Your code should accept a list of points (ordered pairs (x_i, y_i) of floats) and return the two points that are closest together. (iii) Show that this algorithm has temporal complexity in O(n^2) (where the fundamental operations include basic arithmetic operations +, -, times, /, assigning a value to a variable or to a given position in a list, looking up the value of a particular element at a given position in a list, comparing two values, and incrementing a value). Surprisingly, there is a O(n log n) algorithm for solving this problem (see [KT05, 5.4]).

Expert Answer

 

Solution=====================

1) Square root is not important, as we only need to know, which two points are relatively closer. Even if we stop to the of the distance formula’s step, where both x and y are squared and added. We can get away with using this “distance^2” for comparisons, rather than square rooting them to “distance”.

2)

def getClosestPair(pairs):
point1=()
point2=()
smallestDistanceSq=sys.maxint

for i in range(len(pairs)):
for j in range(i+1,len(pairs)):
xDistance=pairs[i][0]-pairs[j][0]
yDistance=pairs[i][1]-pairs[j][1]
#just comparing with squares, no need of rooting
distanceSq=(xDistance*xDistance)+(yDistance*yDistance)

if(distanceSq<smallestDistanceSq):
point1=pairs[i]
point2=pairs[j]
smallestDistanceSq=distanceSq

print(point1)
print(point2)
print(smallestDistanceSq)

Question & Answer: Using Python, please answer all the questions:)..... 1

3)As we can see that, the outer loop iterates for each number of pairs(N), while the inner loop also does the same. Making it N*N = O(N^2). Since the complexity of other operations(like +,- etc.) are trivial/constant to this, they as per rule, are simply discarded for computing time complexity.

Still stressed from student homework?
Get quality assistance from academic writers!