# CS21: Quiz 5 Study Guide

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

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

What is `log(1024,2)`

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

?

Place these algorithm classes in order from best to worst: `N`

, `logN`

, `N*N`

, `NlogN`

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

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

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

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

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

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

?

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

- linear search
- binary search
- merge sort
- selection sort