- Top-down design
- File reading
- Lists of lists
- Using nested loops
- Searching: linear search and binary search
- Sorting: bubble sort and selection sort
- Swapping two values in a list
- Analysis of algorithms/big-O notation (
*O*(1) vs*O*(*l**o**g*(*n*)) vs*O*(*n*) vs*O*(*n*⋅*l**o**g*(*n*)) vs*O*(*n*^{2}))

- Assume that the following assignment has been made:

`L=[["cat", "mammal"], ["boa", "reptile"], ["dove", "bird"], ["dog", "mammal"]]`

Show the value and type of each expression given below:

```
VALUE TYPE
----- ----
len(L)
L[1]
L[1][0]
L[0][1] == L[3][1]
L[0][1] + "-" + L[0][0]
```

- What would the output of the following be?

```
for i in range(2):
for j in range (3):
print("i:%d j:%d" % (i,j))
```

- 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
`N*N`algorithm (T/F) - The number of times N can be divided by 2 (before reaching 1) is log base-two of N (T/F)

How many steps would it take to do binary search on a list of size 1 million when the item you are searching for is NOT in the list?

How many steps would it take to do linear search on a list of size 1 million when the item you are searching for is NOT in the list?

Binary search is much faster than linear search, so why don’t we use it for every search problem?

For each iteration of the loop in

`binarySearch(x, L)`

, show the*index*values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?

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

- For each iteration of the loop in
`binarySearch(y, L)`

, show the*index*values for low, high, and mid, and the value stored at location mid. What will be returned by this function call?

```
y = 4
L = [10, 12, 14, 21, 37, 44, 45, 46, 58, 67, 99]
0 1 2 3 4 5 6 7 8 9 10
low | high | mid | L[mid]
-------------------------
| | |
| | |
| | |
| | |
```

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

```
def indexOfSmallest(ls):
"""
Inputs: A list of values
Returns: The index of the smallest item in the list, -1 if the list
is empty
Purpose: To find the location of the smallest item in the given list
"""
# complete this function
```

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

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

Write an expression for the asymptotic runtime of `oneLoop`

, in terms of the length *n* of the list `L`

.

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

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

- Show how the following list would be changed after bubble sort does one iteration of the outer loop.

`[17, 4, 19, 3, 11, 8]`

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

- linear search
- binary search
- bubble sort
- selection sort