## Quiz 5 Study Guide

Quiz Study Guides are provided as a courtesy. You may work with other students on the questions, and ask questions about the guide during evening ninja help sessions, on piazza, or during meetings with faculty and staff. We do not provide full solutions to the quiz guides.

You are responsible for all material covered through the end of Week 11 (recursion).

In addition to all concepts from Quiz 4, you should understand the following:

### Python concepts

• Searching: linear search and binary search

• Analysis of algorithms/big-O notation:

• O(1) — constant time

• O(\log N) — logarithmic (ex: binary search)

• O(N) — linear (ex: linear search)

• O(N^2) — quadratic (ex: bubble sort)

• Sorting: bubble vs selection sort

• Swapping two values in a list

• Recursion

• base case

• recursive call

• recursion on numbers, strings, and lists

### You should be able to

• compare different runtime analyses for algorithms

• design a recursive function

• draw the call stack for a recursive function

### Practice problems

1. What would the output of the following code be?

``````for i in range(2):
for j in range (3):
print("i:%d j:%d" % (i,j))``````
2. 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^2 algorithm (T/F)

• The number of times N can be divided by 2 (before reaching 1) is \log_2 N (T/F)

3. 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?

4. 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?

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

6. 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]
- - - - - - - - - - - - -
|      |     |
|      |     |
|      |     |
|      |     |```
7. 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]
- - - - - - - - - - - - -
|      |     |
|      |     |
|      |     |
|      |     |```
8. 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``````
9. 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)``````
10. Which algorithm requires time directly proportional to the size of the input list?

• linear search

• binary search

• bubble sort

• selection sort

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

12. Show how the following list `L=[17,4,19,3,11,8]` would be changed after selection sort does its first 3 swaps:

For concreteness, here is some Python code for selection sort:

``````def selectionSort(L):
for j in range(len(L)):
ios = j       # index of smallest item so far
for i in range(j+1,len(L)):
if L[i] < L[ios]:
ios = i
# swap them
L[j],L[ios] = L[ios],L[j]``````
13. Write a recursive function `longestWord(words)` that returns the longest word in `words`, a list of strings. You can assume that `words` contains at least one word.

Then, draw the stack as it would look at its largest (i.e, the deepest part of the recursion when it hits a base case), when the function is called on the list `['awesome', 'recursive', 'code']`.