Quiz 5 Study Guide

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

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

Python concepts

  • Analysis of algorithms, and run times:

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

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

    • \$N^2\$ — quadratic (e.g. selection sort)

  • Searching: linear vs binary search

  • Sorting: bubble vs selection sort

  • Swapping two values in a list

You should be able to

  • compare different runtime analyses for algorithms

  • trace the execution of different searching and sorting algorithms

Practice problems

  • NOTE: There are additional search-specific questions in the searchWorksheet.txt file in your week 10 class notes directory.

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

      • linear search

      • binary search

      • bubble sort

      • selection sort

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

      for i in range(2):
    for j in range(3):
        print("i:%d j:%d" % (i,j))

    3. Consider a similar pair of nested loops in a function:

      def loops(N):
    for i in range(N):
        for j in range(N):
            print("i:%d j:%d" % (i,j))

      In terms of the parameter \$N\$, how many times will this function print given, i.e., is the run time, logarithmic, linear, quadratic, or something else?

    4. Consider the following function, oneLoop(L), which is similar to the inner loop from bubble sort:

      def oneLoop(L):
   for j in range(len(L)-1):
      if L[j] > L[j+1]:
         tmp = L[j+1]
         L[j+1] = L[j]
         L[j] = tmp

      Suppose we run oneLoop on the list L=[17,4,19,3,11,8]. What are the new contents of L?

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

    6. True/False questions:

      • Linear search requires a number of steps proportional to the size of the list being searched (T/F)

      • The python in operator performs a binary search (T/F)

      • Binary search is an O(N) algorithm (T/F)

      • The number of times N can be divided by 2 before reaching 1 is the log (base 2) of N (T/F)

    7. How many steps would it take to do binary search on a list of size 1 million, when the item you are searching for is NOT in the list?

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

    9. For each iteration of the loop in binarySearch(x, L), 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
L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]
      0   1   2   3   4   5   6   7   8   9  10

low | high | mid | L[mid]
- - - - - - - - - - - - -
    |      |     |
    |      |     |
    |      |     |
    |      |     |

    10. For each iteration of the loop in binarySearch(y, L), 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
L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]
      0   1   2   3   4   5   6   7   8   9  10

low | high | mid | L[mid]
- - - - - - - - - - - - - -
    |      |     |
    |      |     |
    |      |     |
    |      |     |