Quiz 5 Study Guide

You are responsible for all material covered through November 27 when we finished talking about recursion. You will not need to write your own classes on this quiz.

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

Python concepts

Searching: linear search and binary search
Sorting: bubble sort and selection sort
Swapping two values in a list
Analysis of algorithms, and run times:
- \$\log N\$ — logarithmic (binary search)
- \$N\$ — linear (linear search)
- \$N^2\$ — quadratic (selection sort, bubble sort)
Recursion
- base case
- recursive call
- recursion on numbers, strings, and lists
- recursion vs iteration

You should be able to

trace the execution of different searching and sorting algorithms
compare different runtime analyses for algorithms
trace the execution of a recursive function
write a recursive function that takes a number, string or list as a parameter

Practice problems

Trace the values of high, low, and mid, and show the return value, for the four examples on the Binary Search worksheet listed in the Readings for Week 9 on the schedule.
Which algorithm requires time directly proportional to the size of the input list?
- linear search
- binary search
- bubble sort
- selection sort

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

Consider a similar pair of nested loops in a function:
```
def loops(N):
    for i in range(N):
        for j in range(N):
            print("i:%d j:%d" % (i,j))
```
In terms of the parameter \$N\$, how many times will this function print given, i.e., is the run time, logarithmic, linear, quadratic, or something else?

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

Suppose we run oneLoop on the list L=[17,4,19,3,11,8]. What are the new contents of L?

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

What would the output of the following code be?

def mystery(n):
    if n == 1:
        # Draw stack here
        return 0
    else:
        return 1 + mystery(n//2)

def main():
    result = mystery(11)
    print("Result: %d" % (result))

main()

Draw a stack diagram to show the contents of the stack just before returning from the base case.

Given the code below:
```
def unknown(lst, idx):
    if (idx >= (len(lst) - 1)):
        return True
    elif lst[idx] > lst[idx + 1]:
        return False
    else:
        return unknown(lst, idx + 1)

def main():
    result = unknown([3, 5, 7, 1], 0)
    print("Result:", result)

main()
```
- What is the return type of the recursive function?
- What is the base case(s)?
- What is the recursive case?
- What is the output of the program show above?
- Provide another list (instead of [3, 5, 7, 1]) with the same length that gives a different output.
- What does the unknown function do, and what would be a better name for this function?
Write a recursive function called numbers that takes a string as its only parameter and returns a new string that contains only the numbers found in that string. For example:
```
>>> numbers("$3,141.59")
"314159"
>>> numbers("52ze47mk3n")
"52473"
>>> numbers("982")
"982"
>>> numbers("quiz")
""
```

Write a recursive function called upper that takes a list of strings as its only parameter and returns a new list of strings where all of the strings in the list have been upper-cased. (Do not mutate the original list of strings.)

>>> lst = ["sunday", "Monday", "35", "f r i d a y"]
>>> upper(lst)
["SUNDAY", "MONDAY", "35", "F R I D A Y"]
>>> lst
["sunday", "Monday", "35", "f r i d a y"]
>>> upper(["PIZZA"])
["PIZZA"]
>>> upper(["stack", "diagrams"])
["STACK", "DIAGRAMS"]