- Sorting: selection, bubble, and insertion sort
- Recursion and iteration
- Merge sort (uses recursion)

- swapping two values in a list
- complexity (big O, number of steps) of searching and sorting algorithms
- string comparisons ("alice" < "zelda")
- recursive function base case
- how variables are stored and function arguments are passed on the stack for recursive functions

- Show how the following list would be changed after selection
sort does its first 3 swaps:
[15, 99, 4, 30, 3, 82, 7, 42]

- 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

- Which algorithm requires time directly proportional to the size of the input?
- linear search
- binary search
- merge sort
- selection sort

- 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.
- Write a function to return the index of the smallest item in a given list.
- 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()