CS21: Quiz 6 Study Guide

In addition to all concepts from Quiz 1, Quiz 2, Quiz 3, Quiz 4, and Quiz 5...

You should understand the following terms and concepts:

• analysis of algorithms/big-O notation (O(n) vs O(log(n)) vs O(n * n))
• 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 do the following:

• compare different runtime analyses for algorithms
• design a recursive function
• draw the call stack for a recursive function

Practice problems:

1. How many steps are required for each of the following?
#############################################
for i in range(N):
for j in range(N):
print("%d %d" % (i,j))
#############################################
while N > 1:
print(N)
N = N/2
#############################################
for i in range(N):
for j in range(10):
print(i, j)
#############################################
1. 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.

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

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

def findLargest(ls, top):
large = 0
for i in range(top+1):#want to include top too
if ls[large] < ls[i]:
large=i
return large

def selectionSort(ls):
N = len(ls)
top = N-1
while top>0:
j = findLargest(ls, top)
swap(ls, j, top)
top = top-1
[15, 99, 4, 30, 3, 82, 7, 42]
1. Show how the following list would be changed after bubble sort does one iteration of the outer loop.
[17, 4, 19, 3, 11, 8]
1. Which algorithm requires time directly proportional to the size of the input list?

• linear search
• binary search
• bubble sort
• selection sort
2. Write a recursive function longestInList(L) that returns the longest string in L, a list of strings. You can assume that L has at least one string.

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']. pdf of solution

3. Write a recursive function countdown(n) which simulates a countdown to a rocket launch. If you call blastoff(4) you should see the following output:

4...
3...
2...
1...
BLASTOFF!

This function is only called for its side-effects (printing), and not its return value.

1. Write a recursive function recBinary(x,L) which implements a recursive version of binary search for item x in list L. It should return True if x is in L, and False otherwise.