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

- complexity (big O, number of steps) of selection/bubble/insertion/merge sort algorithms
- recursive function base case
- how variables are stored and function arguments are passed on the stack for recursive functions

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

- Describe the sorting algorithms we studied in class and show the above list, L, as it is being sorted, using each algorithm.
- 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

- 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()

[Answer (but red arrows aren't needed -- they just show where things get returned)]