15-110 PS4 Sample Solutions - Spring 2018

1. 
(a)
def search(datalist, key):
    index = 0
    while index < len(datalist):
        if datalist[index] == key:
            return index
        if datalist[index] > key:
            return None
        index = index + 1
    return None
(b)
This algorithm is linear (O(n)) so if we increase the number of photographs by 
a factor of 12, then the amount of work will also increase by a factor of 12.
20 seconds * 12 = 240 seconds = 4 minutes

(c)
def is_sorted(datalist):
    for index in range(0, len(datalist)-1):
        if datalist[index] > datalist[index+1]:
            return False
    return True

(d) 
This function is checking each element to see if it is greater than 
itself + 1 (which it never is). Element is not an index! 

2. 
(a)
lo_index  -1   7  11
hi_index  15  15  15   returns 13

(b)
lo_index  -1  -1  -1   1   1
hi_index  15   7   3   3   2   returns None

3.
(a) Since the function uses integer division, it will pick the element
    just to the "left" of the center point. For example, if 
    lo_index = 4 and hi_index = 9, then mid would be 6, not 6.5.

(b) 7 elements: 3 elements examined
    15 elements: 4 elements examined
    31 elements: 5 elements examined
    2**n - 1 elements: n elements examined

4.
(a) Answers for blanks:
    x = datalist[i]
    j >= 0
    datalist[j+1] = datalist[j]
    datalist[j+1] = x

(b) double the data: 4 times as long
    triple the data: 9 times as long