 (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.length1).
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).

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.
 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?

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.length2 do
for j in 0..list.length2 do
if list[j] > list[j+1] then
temp = list[j]
list[j] = list[j+1]
list[j+1] = temp
end
end
end
end
 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]

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.

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)
 If a list has n elements, what is the worstcase 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.
 (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.length2i ? Does this change the worstcase
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.length1
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].
 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
 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
 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.
 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.
 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^{4}  1 elements.)