Introduction.
In this homework, you will compare the running times of
a binary search type of algorithm and a linear search type of algorithm.
In the process, you will also learn a bit about how to generate random
input and how to time Python programs.
Let A be a list of integers. We say that A is bitonic if the elements of A are first strictly increasing and after reaching a maximum value, they are strictly decreasing. More precisely, suppose that A has n elements. Then for some index j, 0 ≤ j ≤ n-1, the array A is strictly increasing up to element A[j], that is,
A[0] < A[1] < ...< A[j]and is strictly decreasing after that, meaning
A[j] > A[j+1] > ... > A[n-1].Note that j could be 0 or n-1. I want you to write two different functions for finding the maximum element in a bitonic array.
def linearFindMax(A):finds the maximum element in the given bitonic array A by simply doing a linear scan of A.
def binaryFindMax(A):should find the maximum element in A using a "binary search like" algorithm, described below, somewhat informally:
Timing your functions.
To get a reliable estimate of the running time of your functions
linearSearch and binarySearch, you should generate random
bitonic arrays of size n = 100000, 150000, 200000, 250000,...,
1000000.
In other words, you should start by generating arrays of size one
hundred thousand and then increase the array size in increments of 50,000
until you reach a million.
Thus you will be considering arrays of 19 different sizes.
For each size n, you should generate 100 different bitonic arrays
of size n,
run binaryFindMax and linearFindMax on each array,
and keep track of the time it takes for each of these functions to
finish finding the maximum element.
Specifically, you want to keep track of the average time each function takes, over
100 runs, with the same size n.
More specifically, you should write two functions
def timeLinearFindMax(): def timeBinaryFindMax():that, as the names suggest, are responsible for timing linearFindMax and binaryFindMax. Here is a description of how you might want to organize your code for timeLinarFindMax.
for n in range(100000, 1050000, 50000): for i in range(0, 100): generate a bitonic array of size n perform linearFindMax on this array, keeping track of the time it takes compute the average time taken by linearFindMax over all 100 arrays of size nIt seems convinient for timeLinearFindMax to return a size-19 list of times, one time for each array size. The code for timeBinaryFindMax would be quite similar. Look at search3.py for an example of how to time programs in python.
Generating Bitonic Arrays of Size n.
The sizes of input arrays we are interested in, are large enough that it is not feasible to generate
them manually (i.e., type them up ourselves).
So we need to write a function to generate a bitonic array of the desired size, say n.
This will be discussed in the discussion section on Monday (3/9) and Tuesday (3/10).
What to submit.
You are required to submit 3 files in a zipped directory (hw7.zip).
The files are: