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:

0. 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.

2. 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]

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

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

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

   • linear search
   • binary search
   • bubble sort
   • selection sort

5. 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

6. 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.

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

8. For additional recursive function problems, try problems on this page.