15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 4 - due Friday, September 28 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.

Exercises

(2 pts) In class, we discussed the linear search algorithm, shown below in Ruby:
```
def contains?(list,key)
  list.each{ |x| return true if x == key }
  return false
end
```
Suppose that we know the additional fact that the list is sorted in ascending order (this means that list[i] < list[i+1], for 0 ≤ i < list.length-1). For example, if our list has the values:
```
[2, 10, 20, 23, 41, 45, 57, 90]
```
then if we want to search for the key 30 using linear search, we can stop when we reach 41 and return false (because we assume that the list is sorted).
1. Revise the method above so that it also returns false immediately as soon as it can be determined that the key cannot be in the list assuming that the list is sorted in increasing order.
2. Suppose that you call the contains? function on three different lists with lengths 2, 4, and 6 where none of the lists contains the key you are looking for. For example:
```
 
>> contains?([2, 10], 100)
=> false
>> contains?([2, 10, 20, 23], 100)
=> false
>> contains?([2, 10, 20, 23, 30, 37], 100)
=> false
```
  Plot a graph such that the x axis of your graph shows the number of items in the list and the y axis shows the comparisons that your function makes. That is, you need to have three points in your graph whose x coordinates are 2, 4, and 6 respectively. Do you observe a straight line or a curve?
3. In general, if the list has n elements, what is the number of elements that would be examined in the worst case for this revised method? Express your answer using big O notation and explain your reasoning.
(2 pts) The following is an implementation of a sort function in Ruby that sorts the elements in list in increasing order.
```
def bsort!(list)
  for i in 0..list.length-2 do
    for j in 0..list.length-2 do
      if list[j] > list[j+1] then 
        temp = list[j]
        list[j] = list[j+1]
        list[j+1] = temp
      end
    end
  end
end
```
1. Trace the function call bsort!([5,4,3,1]), showing the values of i, j, and list after each iteration of the inner for loop is completed. We have started the trace for you with the values of i, j, and list at the end of the first two iterations.
```
   i      j      list
----------------------
   -      -     [5, 4, 3, 1]
   0      0     [4, 5, 3, 1] 
   0      1     [4, 3, 5, 1] 
```
2. What do you observe about the position of 5 at the completion of the inner for loop, i.e., just before i becomes 1? What do you observe about the position of 4 just before i becomes 2? Explain the main idea of this sorting algorithm based on your observation.
3. Based on your answer to the previous question, write down a loop invariant for the outer for loop that captures the main idea of the algorithm. HINT: You can find loop invariant examples in the lecture slides.
(2 pts)
1. If a list has n elements, what is the worst-case order of complexity in big O notation for the bsort! function above? (Think: How many times is list[j] compared to list[j+1]?) Show your work.
2. (corrected) What would change in terms of the number of comparisons we make if we changed the inner loop condition to be j in 0..list.length-2-i? Does this change the worst-case complexity of the algorithm in big O notation? Why or why not?

(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
```
(1 pt) 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.)