Reference no: EM132845419

In this practice, we will be implementing linear search, binary search, and order statistic algorithm discussed in the class. You are required to use python and do not use any method/library that directly performs the task. For help, use the lecture slides. You should be able to explain your code clearly not just read it.

Task 1: Linear Search

This function should return true or false. If the key is present in the array A, then return True, else False.
def LinearSearch(A, key):
# write your code here

1. Generate an array A with 100000 elements consisting of number from 1 to 100000 in ascending order.

2. Provide a value for the key that depicts the best-case runtime for the algorithm. Measure the time using the timing code from the previous assignment. Repeat this process for 3 times and note down the time for each run. Report the average time.

3. Provide a value for the key that depicts the worst-case runtime for the algorithm. Measure the time using the timing code from the previous assignment. Repeat this process for 3 times and note down the time for each run. Report the average time.

Task 2: Binary Search

This function should return true or false. If the key is present in the array A, then return True, else False.

def BinarySearch(A, key):
# write your code here

1. Generate an array A with 100000 elements consisting of number from 1 to 100000 in ascending order.

2. Provide a value for the key that depicts the best-case runtime for the algorithm. Measure the time using the timing code from the previous assignment. Repeat this process for 3 times and note down the time for each run. Report the average time.

3. Provide a value for the key that depicts the worst-case runtime for the algorithm. Measure the time using the timing code from the previous assignment. Repeat this process for 3 times and note down the time for each run. Report the average time.

Task 3: Order Statistic

This function should return the n'th largest number in the array A. Where n=1 means the maximum number.
def OrderStatistic(A, n):
# write your code here

1. Generate an array A with 100000 elements consisting of random numbers in a range from 1 to 100000. The same number can repeat in the array.

2. Find the minimum and maximum number in the array using appropriate values of n.

Attachment:- Linear Search.rar