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 listL=[17,4,19,3,11,8]
. What are the new contents ofL
? 
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 uppercased. (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"]