CS21: Quiz 5 Study Guide

In addition to all concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4...

You should understand the following terms and concepts:

• Searching: linear vs binary search
• Analysis of algorithms/Big-O notation (O(N) vs O(logN) vs O(N*N), etc)
• Analysis of searching algorithms
• string comparisons ("alice" < "zelda")
• list of lists
• Sorting: selection, bubble, and insertion sort
• Analysis of sorting algorithms
• Swapping two values in a list

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 (before reaching 1) is log base-two of N (T/F)

2. What is log(1024,2) in python (don't forget to import the math library)? What about log(2048,2)?

3. Place these algorithm classes in order from best to worst: N, logN, N*N, NlogN

4. Approximately how many iterations will binary search need to find a value in a list of 1 million items?

5. 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)
#############################################

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.

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      ----------------

7. Write a function to return the index of the smallest item in a given list.

8. Show how the following list would be changed after selection sort does its first 3 swaps:

[15, 99, 4, 30, 3, 82, 7, 42]

9. 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

Given the list L = [17, 4, 19, 3, 11, 8], what does L look like after one call to oneLoop(L)?

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

• linear search
• binary search
• merge sort
• selection sort