CS21: Quiz 6 Study Guide

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, and insertion sort
Recursion and iteration
Merge sort (uses recursion)

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

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

Practice problems:

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?
1. linear search
2. binary search
3. merge sort
4. 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()