- (2 pts)
In the lab you saw the linear search algorithm, shown below
in Ruby:
def linear_search(list, key)
len = list.length
index = 0
while index < len 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 descending order (this means that
list[i] >
list[i+1], for 0 ≤ i < list.length-1).
For example, if our list has the values:
[90, 80, 56, 45, 39, 23, 20, 8, 1]
then if we want to search for the key 40 using linear search, we can
stop when we reach 39 and return nil because we assume that the list is sorted.
-
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 descending (decreasing) order.
- Suppose that you call the linear_search 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:
>> linear_search([10, 2], 1)
=> nil
>> linear_search([23, 15, 10, 13], 1)
=> nil
>> linear_search([32, 31, 20, 13, 10, 7], 1)
=> nil
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 function? Express your answer using big O notation and explain your
reasoning.
-
Consider the slightly modified version of the function linear_search above, called linear_search2(list, key).
def linear_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
Which implementation of linear search seems more efficient? Does it change the asymptotic time complexity in terms of big O?Why?
- (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.
[35, 22, 83, 17, 30, 58]
- 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.
- (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 = ["Anna", "Dan", "Ella", "Finn", "Gina", "Ivan", "Karen", "Luke", "Mary", "Nadia", "Oliver", "Perry", "Russell", "Tom", "Ziv"].
- Trace the function above for the function call
bsearch(list, "Gina"),
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, "Tom"),
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, "George"),
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 pts) For this part of the assignment, you will work on a module in the Online Learning Initiative at CMU that will teach you about a new topic called recursion. This module will help you learn the basics about recursion before we cover this topic in class next week.
In order to get credit for this part, you must complete the module by the deadline for the problem set. We will not be grading you on how many questions you get right in the module. Instead, we will be grading you on whether you completed the module on time or not.
To access this module:
- Go to this URL: http://oli.cmu.edu
- If you do not have an
account, click on the "Register" link in the upper right. Click
on the "CMU users sign in here" link.
- If you already have
an account, Sign In: Click on the "CMU users sign in here"
link.
- Enter your course key 15110s13 into the box labeled "Register
for a course" as shown at right.
- Follow the instructions on the My Courses page to get started
on the Recursion module.
- You don't have to do then entire module in one sitting; you can
leave the web site and resume work on it later.