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(i, j)
   #############################################
   while N > 1:
         print(N)
         N = N/2
   #############################################
   for i in range(N):
       for j in range(10):
           print(i, j)
   #############################################

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

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

   [15, 99, 4, 30, 3, 82, 7, 42]

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

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

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

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

6. Write a recursive function longestInList(L) that returns the longest string in L, a list of strings.

   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

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

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

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