22C:80 Programming for Informatics: Homework 7

Homework 7, Due Friday, 3/13 by midnight pm via ICON

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.

The first function,
```
		def linearFindMax(A):
```
finds the maximum element in the given bitonic array A by simply doing a linear scan of A.
The second function,
```
		def binaryFindMax(A):
```
should find the maximum element in A using a "binary search like" algorithm, described below, somewhat informally:
- Examine the "middle" element of A and the elements immediately to its left and immediately to its right.
- Based on this examination, you can determine if you have found the maximum element or if you should search for the maximum element in the left half of the array or if you should search for the maximum element in the right half of the array.

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 n

It 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:

hw7.py, a file containing your Python program. Make sure that your program is clearly commented.
README file, describing (as usual) the status of your program (e.g., does it compile? if it does, does it work correctly? if not, under what circumstances does it break down? how long does it take to run? etc.).
runningTime.doc or runningTime.pdf, a word document or a pdf document containing a listing of the output produced by your program, plots showing clearly the growth in running time as the input size increases for both linearFindMax and binaryFindMax, and 2-3 sentence interpretation of each plot (e.g., based on your plots what can you say about the rate of growth of the running time of each function as a function of the input size? are these what you expected? if so why, if not, why not? etc). You can produce the plots using software such as Excel or Mathematica or Matlab, all of which are available on the machines in 301 MLH.