In addition to the concepts below, you should also know the concepts that were tested on all of the previous quizzes: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5.

You should be able to define and explain the following terms:

• Sorting: selection, bubble, insertion
• Analysis of algorithms (number of steps)
• Big-O notation (O(N) vs O(logN), etc)
• Recursion and iteration
• Merge sort (uses recursion)

You should understand and be able to use the following Python concepts:

• complexity (big O, number of steps) of sorting algorithms (selection, merge, etc)
• recursive function base case
• how variables are stored and function arguments are passed on the stack for recursive functions

Practice problems:

1. Write two versions of each of the following functions...one version using iteration and one using recursion:
   • sum all values in a given list of integers
   • return True if a list is sorted/in order, False if not
   • count/return how many times a given value (v) is found in a list (L)
   • find the largest number in a list
2. Draw a stack diagram for the following program. Show what the stack would look like at it's largest point.

   def main():
       n = 5
       ans = factorial(n)
       print(ans)
   
   def factorial(x):
       if x == 0:
         return 1
       else:
         return x * factorial(x-1)
   
   main()
   

3. If you are running selectionSort() on the following list, L:

   L = [9, 35, 18, 200, 0, 6, 43, 21]
   

   Which of the following represents L after 3 iterations of the outer loop in selectionSort()?

   A. [0, 6, 9, 18, 21, 35, 43, 200]
   B. [0, 6, 9, 200, 18, 35, 43, 21]
   C. [0, 9, 35, 18, 200, 6, 43, 21]
   D. [0, 6, 9, 35, 200, 18, 43, 21]
   

4. Show all output for the following program:

   def printline():
     print("-"*20)
   
   def mystery(L):
     while True:
       nswaps = 0
       for i in range(len(L)-1):
         if L[i] > L[i+1]:
           L[i],L[i+1] = L[i+1],L[i]
           print(L)
           nswaps = nswaps + 1
       if nswaps == 0:
         return
       printline()
   
   L = [22,57,3,30]
   print("initial list:")
   print(L)
   printline()
   mystery(L)
   printline()
   print("final list:")
   print(L)