CS21: Quiz 5 Study Guide

In addition to the concepts below, you should also know the concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4.

This quiz will focus on:

• Searching: linear vs binary search
• Sorting: selection, bubble, insertion
• Analysis of algorithms (number of steps)
• Big-O notation (O(N) vs O(logN), etc)

Practice problems:

1. 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 NlogN algorithm (T/F)
   • The number of times N can be divided by 2 is log base-two of N (T/F)
2. Approximately how many iterations will binary search need to find a value in a list of 1 million items?
3. Place these algorithm classes in order from best to worst: N, logN, N*N, NlogN
4. How many steps are required for each of the following?

   #############################################
   for i in range(n):
     for j in range(n):
       print i, j
   #############################################
   while n > 1:
     print n
     n = n/2
   #############################################
   for i in range(n):
     for j in range(10):
       print i, j
   #############################################
   

5. Show the index values for low, high, and mid for each step in searching the list L for the value x using binary search.

   x = 99
   L = [-20, -12, -4, 1, 7, 44, 45, 46, 58, 67, 99, 145]     low | mid | high
          0    1   2  3  4   5   6   7   8   9  10   11      ----------------
                                                                 |     |
                                                                 |     |
   

6. If you are running selectionSort() on the following list, L:

   L = [9, 35, 18, 200, 0, 6, 43, 21]
   

   Which of the following represents L after 3 iterations of the outer loop in selectionSort()?

   A. [0, 6, 9, 18, 21, 35, 43, 200]
   B. [0, 6, 9, 200, 18, 35, 43, 21]
   C. [0, 9, 35, 18, 200, 6, 43, 21]
   D. [0, 6, 9, 35, 200, 18, 43, 21]
   

7. Given the following assignments:

   L = [["bird", 3], ["cat", 2], ["dog", 4], ["snake", 1]]
   

   What are the value and type of the following expressions:

     (1) L[1]
     (2) L[1][0]
     (3) L[1][1]
     (4) L[0][0] < L[3][0]
     (5) L[1][1] < L[2][1]