15110 Spring 2012 [Cortina/von Ronne]

Problem Set 4 - due Friday, February 17 in class

Reading Assignment

Read sections 4.1-4.5 in chapter 4 of Explorations in Computing.

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, lab section (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.

!!!! NOTE THE CORRECTION IN BOLD IN PROBLEM 1 PART D !!!!

Exercises

(3 pts) In class, we discussed the linear search algorithm, shown below in Ruby:
```
def search(list, key)
        index = 0
        while index != list.length do
                if list[index] == key then
                        return index
                end
                index = index + 1
        end
        return nil
end
```
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 < list.length-1). 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 nil (assuming that the list is sorted).
1. Revise the method above so that it also returns nil 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 array has n elements, what is the number of elements that would be examined in the worst case for this revised method using big O notation? Why?
3. In order to use your new method, you should probably have a method that allows you to check to make sure that the array is sorted in decreasing order before you use the search method. Write a Ruby function sorted? that returns true if an array called list is sorted in decreasing order or false if it is not.
```
def sorted?(list)




end
```
  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 always correct if it returns nil. (HINT: When the loop runs to completion, what is true besides the loop invariant?)
(3 pts) If a list is sorted, 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 Ruby using iteration:
```
def bsearch(list, key)
    min = 0
    max = list.length-1
    while min <= max do
        mid = (min+max)/2
        return mid if list[mid] == key
        if key > list[mid] then
            min = mid + 1
        else
            max = mid - 1
        end
    end
    return nil
end
```
Let list = [4, 10, 12, 16, 21, 24, 30, 33, 46, 58, 60, 72, 73, 85, 96].
1. Trace the function above for the function call bsearch(list, 21), showing the values of min and max 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 min and max.
```
 min     max
--------------
   0      14
```
2. Trace the function above for the function call bsearch(list, 85), showing the values of min and max 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 min and max.
```
 min     max
--------------
   0      14
```
3. Trace the function above for the function call bsearch(list, 11), showing the values of min and max 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 min and max.
```
 min     max
--------------
   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? Give at least 2 examples to illustrate your answer. (HINT: The list in the previous problem has 15 = 2⁴ - 1 elements.)

(2 pts) Consider the following sorting function written in Ruby:

def swap(list, i, j)
    #swaps list[i] with list[j]
    temp = list[i]
    list[i] = list[j]
    list[j] = temp
end

def mystery_sort!(list)
    for i in 0..list.length-2 do
        for j in i+1..list.length-1 do
            if list[i] > list[j] then 
                swap(list, i, j)
            end
        end
    end
end

Trace the mystery sort function for the following list, showing the list after every swap is done.
```
[45, 32, 86, 17, 20, 59]
```
If a list has n elements, what is the worst-case order of complexity in big O notation for the mystery sort function? (THINK: How many times is list[i] compared to list[j]?) Show your work.