The following algorithm examines all the components in a given array to check for the existence...

Transcribed Image Text:

The following algorithm examines all the components in a given array to check for the existence of any two numbers, where one of them is the square of the other, in the given array or not. For example 1: input: A[9,5,28,25,47, 55] → output: true For example 2: input: A[24,15,18,18,42, 22] → output: false In example 1 the output is True because (5 and 25), where 25 is the square value of 5, while the output of example 2 is False because there is no any pair of numbers that meets this condition. • Input: An array A[0...n-1] • Output: Return True if there exist any two numbers, where one of them is the square of the other in the array, False otherwise a) Design a brute force algorithm to solve this problem (5 marks) and analyze its complexity. [explain your answer] (2 marks) b) Design a more efficient algorithm to do the same job (10 marks) analyze the complexity of your algorithm [explain your answer] (3 marks) c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case] The following algorithm examines all the components in a given array to check for the existence of any two numbers, where one of them is the square of the other, in the given array or not. For example 1: input: A[9,5,28,25,47, 55] → output: true For example 2: input: A[24,15,18,18,42, 22] → output: false In example 1 the output is True because (5 and 25), where 25 is the square value of 5, while the output of example 2 is False because there is no any pair of numbers that meets this condition. • Input: An array A[0...n-1] • Output: Return True if there exist any two numbers, where one of them is the square of the other in the array, False otherwise a) Design a brute force algorithm to solve this problem (5 marks) and analyze its complexity. [explain your answer] (2 marks) b) Design a more efficient algorithm to do the same job (10 marks) analyze the complexity of your algorithm [explain your answer] (3 marks) c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case]

Answer rating: 100% (QA)

a Brute Force AlgorithmA brute force algorithm to solve this problem would involve checking all poss... View the full answer