Here are some sample questions and concepts for the upcoming quiz that you might wish to try out. Obviously, we assume that you still remember the concepts covered in the earlier quizzes!

You should understand the following topics:

• Lists of lists
• Searching: linear vs binary
• 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:
   • In the worst case, Linear search requires a number of steps proportional to the size of the list being searched (True/False)
   • The python in operator performs a binary search (True/False)
   • Binary search is an NlogN algorithm (True/False)
   • The number of times N can be divided by 2 is log base-two of N (True/False)
   • Binary search is always faster than Linear search (True/False)
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. What is log(1024,2) in python? What about log(2048,2)?
5. How many steps are required for each of the following? Assume that n is a postive integer.

   #-------------------------------------------
   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
   #-------------------------------------------
   i = 0
   while i < n:
     print i
     i = i + 1
   #-------------------------------------------
   while n > 0
     print n
   #-------------------------------------------
   

6. Show the index values for low, high, and mid for each step in searching the list L for the value x using binary search. The indices for L are shown above the list.

        0   1   2   3   4   5   6   7   8
   L = [10, 17, 44, 45, 46, 58, 67, 99, 122]
   x = 99
   

7. 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 the algorithm:

   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]
   

8. If you are running insertionSort on the following list, L:

   L = [22, 41, 56, 7, 79, 75, 89]
   

   Which value in the list would be the first one to be swapped?
   What would it be swapped with?

9. If you are running bubbleSort on the following list, L:

   L = [22, 41, 56, 7, 79, 75, 89]
   

   Show how the list would change after completing one iteration of the outer loop of the algorithm.

10. Given the following assignment:

       ls = [[1, "dog"], [3, "fish"], [2, "cat"]]
    

    What are the value and type of the following expressions:

      (1) len(ls)
      (2) ls[1]
      (3) ls[1][1]
      (4) ls[1][0] < ls[2][0]
      (5) ls[2][1] + ls[1][1]
    

    What would ls[0].append("woof") do?