- 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

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