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:

• Analysis of algorithms (number of steps, O(N) vs O(logN) vs O(N*N), etc)
• Sorting: selection, bubble, and insertion sort
• Swapping two values in a list
• Recursion and iteration

Practice problems:

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

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

2. Consider the following function, oneLoop, which is similar to the inner loop from bubble sort:

   def oneLoop(ls):
     print "in oneLoop"
     for j in range(len(ls)-1):
       if ls[j] > ls[j+1]:
         tmp = ls[j+1]
         ls[j+1] = ls[j]
         ls[j] = tmp
   

   (1) Given the list ls = [17, 4, 19, 3, 11, 8], what is ls after one call to oneLoop(ls)?

   (2) Given the following main function, trace through its execution showing all program output and drawing the stack right before the call to function oneLoop returns:

   def main( ):                    
     print "in main"
     my_list = [6, 8, 19, 3, 7]
     print my_list
     oneLoop(my_list)
     print my_list 
   

3. Which algorithm requires time directly proportional to the size of the input?
   1. linear search
   2. binary search
   3. merge sort
   4. selection sort
4. Write a sort function (any sort) that takes in a list and sorts it in place. Show what a call to your sort function would look like from main.
5. 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
6. 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()