Week 13 Quiz

Predict, then check: what does this program print?

def linear_search(items, target):
    comparisons = 0
    for i in range(len(items)):
        comparisons = comparisons + 1
        if items[i] == target:
            return i, comparisons
    return -1, comparisons

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(linear_search(pages, 21))

Select one.

• (4, 5)
• (5, 4)
• (4, 3)
• (21, 5)

Predict, then check: 22 is not in the list. What does this program print?

def linear_search(items, target):
    comparisons = 0
    for i in range(len(items)):
        comparisons = comparisons + 1
        if items[i] == target:
            return i, comparisons
    return -1, comparisons

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(linear_search(pages, 22))

Select one.

• (−1, 0)
• (−1, 8)
• (None, 8)
• (−1, 7)

On the sorted list 1 to 16, made with numbers = list(range(1, 17)), the course's linear search and binary search each look for 13. How many comparisons does each one make?

Select one.

• Linear 13, binary 13
• Linear 4, binary 13
• Linear 13, binary 4
• Linear 12, binary 4

Predict, then check: in this search for 21, which middle indexes does mid take on the first two passes?

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    comparisons = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        comparisons = comparisons + 1
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(binary_search(pages, 21))

Select one.

• 0, then 1
• 15, then 27
• 3, then 4
• 3, then 5

Predict, then check: the list holds a 3 at index 3, but it is not sorted. What does this program print?

def binary_search(items, target):
    lo = 0
    hi = len(items) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = [27, 8, 40, 3, 15]
print(binary_search(data, 3))

Select one.

• −1
• 3
• 0
• IndexError

Predict, then check: this version starts hi at len(items) instead of len(items) - 1. What happens when it runs?

def binary_search(items, target):
    lo = 0
    hi = len(items)
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

pages = [3, 8, 12, 15, 21, 27, 34, 40]
print(binary_search(pages, 21))
print(binary_search(pages, 41))

Select one.

• It prints 4, then −1
• It prints 4, then stops with IndexError
• It prints 4, then 7
• It stops with IndexError before printing anything

In the course's binary search for 22 on the reading log's page counts, the third pass checks index 4, which holds 21. Since 21 is less than 22, lo becomes 5 while hi is 4. What happens next?

Select one.

• The loop runs once more with mid = 5
• The function returns 4 because 21 is closest
• The loop test lo <= hi is False, so the loop stops and the function returns (−1, 3)
• The loop never stops, because lo and hi never meet

Predict, then check: what is the first line this program prints?

def selection_sort(items):
    items = items[:]
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
        print("pass", i + 1, items)
    return items

print(selection_sort([27, 8, 40, 3, 15]))

Select one.

• pass 1 [3, 8, 40, 27, 15]
• pass 1 [8, 27, 40, 3, 15]
• pass 1 [3, 8, 15, 27, 40]
• pass 1 [3, 27, 8, 40, 15]

The course ran a linear search, a binary search, and selection sort on lists that doubled in length. Select every statement that is true.

Select every option that applies.

• Binary search is logarithmic time: its worst case went 4, 5, 6 as the list doubled from 8 to 16 to 32 items.
• Selection sort is quadratic time: its comparisons went from 45 to 190 when the list doubled from 10 to 20 items.
• Big-O is the exact step count, so binary search finding 13 in 4 comparisons and 16 in 5 puts them in different growth classes.
• Reading pages[4] is linear time, because the list it reads from holds 8 items.

True or false: an already sorted list of 5 items, such as [3, 8, 15, 27, 40], takes the course's selection sort fewer than 10 comparisons.

True or false.

• True
• False