Python 3: Part B needed Write a function "closest_pair" to determine the closest pair in Theta(N^2)...

Python 3: Part B needed

Write a function "closest_pair" to determine the closest pair in Theta(N^2) time, return that pair as a tuple. The closest pair is defined as the pair of numbers whose difference is the minimum of all pairs in the list. For example:

Given the list [ 3,6,4,10,23] the closest pair would be (3,4) since the difference is just 1.

Given the list [10, 45, 55, 42, 20], the closest pair would be (42,45) since the different is just 3

Given the list [4,10,6,7,10,5], the closest pair would be (10,10) since the distance is zero.

B) Write a function "fast_closest_pair" to determine the closest pair (same as in part A), except this time you should do it in better than Theta (N^2).

Expert Solution

Hello, I am putting the code for Both A as well as B. Where I put the comment also for your better understanding where first program is taking O(n*n) time complexity and second will take O(n*log n) time complexity. which is better than first one. Although you have any doubt, feel free to comment down and if you like my answer, don't forget to give me upvote.

Thank you, Enjoy your answer.

# Answer : A)

mylist = [4,6,10,7,10,5];

tuplee = (mylist[0], mylist[1])
minimum = abs(mylist[0] - mylist[1])


# this loop will take O(n)
for i in range(0, len(mylist)-1):
        # below loop also will take O(n) times
        # As It is using nested loop 
        # So here complexity will be multiplied.
        # so complexity = O(n)* O(n) = O(n^2)
        for j in range(i+1, len(mylist)):
                a = mylist[i]
                b = mylist[j]
                if(minimum > abs(a-b)):
                        minimum = abs(a-b)
                        tuplee = (a, b)
print("using n*n time complexity: ",tuplee)

Now Second Program:


mylist = [4,6,10,7,10,5];


# this will take O(n*logn)
mylist = sorted(mylist)

tuplee = (mylist[0], mylist[1])
minimum = abs(mylist[0] - mylist[1])

tuplee = (mylist[0], mylist[1])

# this will take O(n), but it is not using nested loops
# so, here Complexity will added.
# so complexity = O(n*log n) + O(n) = O(n*log n)
# which means this is better than first one
for i in range(1,len(mylist)):
        a = mylist[i-1]
        b = mylist[i]

        if(minimum > abs(a-b)):
                minimum = abs(a-b)
                tuplee = (a, b)
print("using n*log n time complexity: ",tuplee)

Hope You understood this answer.

venereology answered 2 years ago

Python: Write a recursive function that accepts an integer argument, n. The function should display n...

Python: Write a recursive function that accepts an integer argument, n. The function should display n lines of asterisks on the screen, with the first line showing 1 asterisk, the second line showing 2 asterisks, up to the nth line which shows n asterisks. Test the function.

PYTHON 3: Write a recursive function that takes a non-negative integer n as input and returns...

PYTHON 3: Write a recursive function that takes a non-negative integer n as input and returns the number of 1's in the binary representation of n. Use the fact that this is equal to the number of 1's in the representation of n//2 (integer division) plus 1 if n is odd. >>>numOnes(0) 0 >>>numOnes(1) 1 >>>numOnes(14) 3

This is a python question. Write a function mult_table(n) that consumes a natural number n and...

This is a python question. Write a function mult_table(n) that consumes a natural number n and returns the n+1 by n+1 multiplication table (where each entry in the inner list is equal to the product of which list it is and the inner list position number, or in other words, the product of the row and column numbers). Use accumulative recursion. def mult_table(n) ''' Returns the n+1 by n+1 multiplication table mult_table: Nat => (listof (listof Nat)) Examples:...

Prove that 1+ cos theta + cos 2theta + .... cos ntheta = 1/2 + (sin(n+1/2)theta)/2sin(theta/2)

Python language: Write a function dice(n) that returns a list with the results of n dice...

Python language: Write a function dice(n) that returns a list with the results of n dice rolls conducted with a six sided dice. Use Numpy's random number functions to do this (Hint: use randint() within numpy's random module). i.e. dice(3) returns something like [2,3,5] to indicate the first dice obtained a 2, the second a 3 etc

Write a function in python that takes in an integer n and computes the left hand...

Write a function in python that takes in an integer n and computes the left hand Riemann sum of the function f(x) = x^2 on the interval [0,1]. Hint: compute the error from the true answer

Python: Write the function pixelLuminance that takes 3 integers r, g, and b, each between 0...

Python: Write the function pixelLuminance that takes 3 integers r, g, and b, each between 0 and 255 (inclusive), representing the red, green, and blue intensity of a pixel and returns the luminance of this pixel as an integer. The function expects each parameter r, g, and b to be an integer in the interval [0,255]. You should use assertions to enforce this constraint.

write a python function that takes a number as input argument, and that tries to determine...

write a python function that takes a number as input argument, and that tries to determine two other integers, root and pwr, such that root**pwr is equal to the integer passed as an argument to the function. Consider that pwr > 1. The function should return the values of root and pwr, as a string in the form root**pwr. For example, when the passed argument is 8, the function should return the string ‘2**3’. When the passed input argument does...

PYTHON! Exercise 3 - Total Line length Write a python function that will return the total...

PYTHON! Exercise 3 - Total Line length Write a python function that will return the total length of line that passes through any number of provided points ( (x,y) ). The points should be passed as individual tuples or lists. The function should also have a parameter (True or False) to indicate whether the line should start from the origin, and that parameter should default to False. If True, the returned value should include the distance from the origin to...

The coding must be formatted in Python. Write a function matrix_power(A, n) that computes the power...

The coding must be formatted in Python. Write a function matrix_power(A, n) that computes the power An using Boolean arithmetic and returns the result. You may assume that A is a 2D list containing only 0s and 1s, A is square (same number of rows and columns), and n is an integer ≥ 1. You should call your previously written matrix multiply boolean function. Example: Let R = [ [0, 0, 0, 1], [0, 1, 1, 0], [0, 0, 0,...

Question