15110 SUMMER SESSION TWO - 2014

Problem Set 4 - due Friday, July 11 at 9:00AM in class

Instructions

Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in.
On the first page of your homework, include your name, andrew ID, and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

NOTE CORRECTIONS FOR SYNTAX ERRORS

(3 pts) In class, we discussed the linear search algorithm, shown below in Python:
```
def search(list, key):
    index = 0
    while index != len(list):
        if list[index] == key:
            return index
        index = index + 1
    return None
```
Suppose that we know the additional fact that the list is sorted in decreasing order (this means that list[i] > list[i+1], for 0 ≤ i < len(list)-1). [CORRECTION] For example, if our list has the values:
```
[94, 82, 79, 73, 61, 45, 37, 25]
```
then if we want to search for the key 70 using linear search, we can stop when we reach 61 and return None (assuming that the list is sorted).
1. Revise the function above so that it also returns None immediately as soon as it can be determined that the key cannot be in the list assuming that the list is sorted in decreasing order.
2. If the list has n elements, what is the number of elements that would be examined in the worst case for this revised function using big O notation? Why?
3. In order to use your new function, you should probably have a method that allows you to check to make sure that the list is sorted in decreasing order before you use the search method. Write a Python function is_sorted(list) that returns True if a given list is sorted in decreasing order or False if it is not.
```
def is_sorted(list):
```
  HINT: Set up a for loop to compare list[i] with list[i+1]. If you ever get two neighboring elements that are not in decreasing order, then the whole list cannot be sorted. Be careful with the range you use for i.
4. A loop invariant for this function is: list[0..index-1] does not contain the key. That is, at the end of each iteration, the key is not in positions 0 through index-1 in the list. Using the loop invariant, explain why the search function is correct if it returns None. (HINT: When the loop runs to completion, what is true besides the loop invariant?)
(3 pts) If a list is sorted in increasing order, we can search the list using another algorithm called Binary Search. The basic idea is to find the middle element, then if that is not the key, you search either the first half of the list or the second half of the list, depending on the half that could contain the key. The process is repeated iteratively until we either find the key or we run out of elements to examine.
Here is an implementation of binary search in Python using iteration:
```
def bsearch(list, key):
    lo_index = 0
    hi_index = len(list)-1
    while lo_index <= hi_index:
        mid = (lo_index+high_index)//2
        if list[mid] == key:      # CORRECTED SYNTAX
            return mid
        if key > list[mid]:
            lo_index = mid + 1
        else:
            hi_index = mid - 1
    return None
```
Let list = [5, 11, 13, 17, 22, 25, 31, 34, 47, 59, 61, 73, 74, 86, 97].
1. Trace the function above for the function call bsearch(list, 22), showing the values of lo_index and hi_index after each iteration of the while loop is completed. Also write down the value returned by the function. We have started the trace with the initial values of lo_index and hi_index.
```
lo_index hi_index
-----------------
   0       14
```
2. Trace the function above for the function call bsearch(list, 86), showing the values of lo_index and hi_index after each iteration of the while loop is completed. Also write down the value returned by the function. We have started the trace with the initial values of lo_index and hi_index.
```
lo_index hi_index
-----------------
   0       14
```
3. Trace the function above for the function call bsearch(list, 12), showing the values of lo_index and hi_index after each iteration of the while loop is completed. Also write down the value returned by the function. We have started the trace with the initial values of lo_index and hi_index.
```
lo_index hi_index   
-----------------
   0       14
```
(2 pts) Using the binary search function from the previous problem, answer the following questions clearly and concisely.
1. If the list has an even number of elements, how does the function determine the location of the "middle element"? Give an example to illustrate your answer.
2. If the list has 2^N-1 elements, where N > 0, what is the maximum number of elements that will be compared to the key for equality, in terms of the variable N? Give at least 2 examples to illustrate your answer using different values for N. (HINT: The list in the previous problem has 15 = 2⁴ - 1 elements.)
(2 pts) Consider the following sorting function written in Python:
```
def swap(list, i, j):
    #swaps list[i] with list[j]
    temp = list[i]
    list[i] = list[j]
    list[j] = temp

def mystery_sort(list):
    for i in range(0,len(list)-1):      #CORRECTED SYNTAX
        for j in range(i+1,len(list)):  #CORRECTED SYNTAX
            if list[i] > list[j]:    #compare two elements of the list
                swap(list, i, j)     #swap if out of order
```
1. Trace the mystery sort function for the following list, showing the list after every swap is done. (HINT: You can use python3 to help you here!)
```
[47, 30, 89, 12, 26, 55]
```
2. The amount of work this function does is dependent on the number of times two elements are compared with each other. If a list has n elements, with n > 0, what is the worst-case order of complexity in big O notation for the mystery sort function? (THINK: What is the maximum number of times elements are compared with each other, in terms of the variable n?) Show your work.