Homework 8

Details

For each problem make sure you clearly and neatly show all of your work! Each part/problem is worth 5 points.

1. Write an algorithm that computes the average of a list of numbers A. Assume there are n numbers on the list, and you may access them by using A[i] notation or by saying something like the ith item on the list A. (Recall that the average is the sum of all of the numbers on a list divided by the number of numbers on the list.)
2. Consider the following list:
   54, 32, 86, 19, 30, 12, 43, 10, 28, 3, 95, 6, 12, 52, 11
   In each of the following, keep in mind that your goal is to convince me that you understand each algorithm. Therefore, provide enough work to make it absolutely clear what is going on.
   1. Demonstrate the steps that linear search would take to search for the number 43 on the list. How many steps did it take?
   2. Demonstrate the steps selection sort would use to sort the list. Hint: You should have about 15 steps, each one showing the contents of the array.
   3. Demonstrate the steps of binary search to locate 43 on the sorted version of the list. Very clearly indicate which values are accessed and present your work in a way that makes it obvious why the algorithm is done when it is. How many steps did it take?
   4. If I gave you a new list with 100 elements on it and all you had to do was determine whether or not a given number is on that list, would it be better to (a) use linear search or to (b) sort the list (using selection sort or merge sort) and then use binary search? Clearly justify your answer.