Quiz 5 Study Guide

You are responsible for all material covered through the end of Week 10.

Python concepts

In addition to all concepts from Quiz 4, you should understand the following:

  • Searching: linear search, binary search

  • Sorting: bubble sort, selection sort

  • Analysis of algorithms, and run times:

    • \(\log N\) — logarithmic (e.g., binary search)

    • \(N\) — linear (e.g., linear search)

    • \(N^2\) — quadratic (e.g., bubble/selection sort)

You should be able to:

  • trace the execution of linear and binary search

  • trace the execution of selection sort and bubble sort

  • compare different runtime analyses for algorithms

Practice problems

  1. For each iteration of the loop in binarySearch(x, lst), show the index values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?

    x = 67
lst = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]
index   0   1   2   3   4   5   6   7   8   9  10

low | high | mid | lst[mid]
- - - - - - - - - - - - -
    |      |     |
    |      |     |
    |      |     |
    |      |     |

  2. For each iteration of the loop in binarySearch(y, lst), show the index values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?

    y = 4
lst = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]
index   0   1   2   3   4   5   6   7   8   9  10

low | high | mid | lst[mid]
- - - - - - - - - - - - - -
    |      |     |
    |      |     |
    |      |     |
    |      |     |

  3. Binary search is much faster than linear search, so why don’t we use it for every search problem?

  4. Which algorithm requires time directly proportional to the size of the input list?

    • linear search

    • binary search

    • selection sort

  5. Consider a pair of nested loops in a function:

    def loops(N):
    for i in range(N):
        for j in range(N):
            print("hello")

    In terms of the parameter \(N\), how many times will the function print "hello"? That is, is the run time logarithmic, linear, quadratic, or something else?

  6. Show how the list L=[17,4,19,3,11,8] would be changed after selection sort does its first 3 swaps.

  7. What would the output of the following code be?

    def mystery(lst, idx):

    modded = False

    if lst[idx] % 2 == 0:
        lst[idx] = lst[idx] + 1
        modded = True

    return modded


def main():

    L = [2, 3, 4, 5, 6]
    k = 2
    ans = mystery(L, k)

    print(L)
    print("Answer: %s"  % (ans))

main()

    Draw the stack diagram to show the contents of the stack just before returning from mystery. What is the output of the program?