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 sorting algorithms (selection, merge, etc)
recursive function base case
how variables are stored and function arguments are passed on the stack for recursive functions

Practice problems:

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

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]

Show all output for the following program:

def printline():
  print("-"*20)

def mystery(L):
  while True:
    nswaps = 0
    for i in range(len(L)-1):
      if L[i] > L[i+1]:
        L[i],L[i+1] = L[i+1],L[i]
        print(L)
        nswaps = nswaps + 1
    if nswaps == 0:
      return
    printline()

L = [22,57,3,30]
print("initial list:")
print(L)
printline()
mystery(L)
printline()
print("final list:")
print(L)