# 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, insertion
• Analysis of algorithms (number of steps)
• Big-O notation (O(N) vs O(logN), etc)
• Recursion and iteration
• Merge sort (uses recursion)

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

• 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

#### Practice problems:

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