# 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. Many of the earlier concepts -- especially functions -- are fundamental to what we've been studying recently.

#### 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
(3) ls
(4) ls < ls
(5) ls + ls
```