Practice Quiz6

---

Notes:

• In addition to the material covered here, quiz6 will also include the FRs that would have been on quiz5.
• Including the FitBs, this practice quiz should take 35 minutes.

---

First, print out and complete S25 Quiz 10A

• You can skip the bonus questions.

---

Next, print out and complete these FitB questions:

# FitB

Fill in the blanks with the missing code for the following
examples taken from the course notes.

# FitB #1:

def gcd(x, y):
    # Euclid's (very fast) algorithm:
    if y == 0:
        return x
    else:
        return gcd(_____________________________________)


# FitB #2:

def move(n, source, target, temp):
    if n == 1:
        return [(source, target)]
    else:
        return (move(_________________________________________) +
                move(  1, source, target, temp) +
                move(n-1, temp,   target, source))

def solveTowersOfHanoi(n):
    return move(n, 0, 2, 1)

# FitB #3:

def floodFillHelper(board, row, col, oldValue, newValue):
    rows, cols = len(board), len(board[0])
    if ((row < 0) or (row >= rows) or
        (col < 0) or (col >= cols) or

        (___________________________________________________)):
        return
    else:
        board[row][col] = newValue
        floodFillHelper(board, row-1, col, oldValue, newValue) # up
        floodFillHelper(board, row+1, col, oldValue, newValue) # down
        floodFillHelper(board, row, col-1, oldValue, newValue) # left
        floodFillHelper(board, row, col+1, oldValue, newValue) # right

# FitB #4:

# assume partition(L) is written for you:

def quickSort(L):
    if len(L) < 2:
        return L
    else:
        smaller, pivot, larger = partition(L)

        return __________________________________________________

# FitB #5:

# assume merge(L, M) is written for you:

def mergeSort(L):
    if len(L) < 2:
        return L
    else:
        i = len(L)//2
        sortedLeftHalf = mergeSort(L[:i])
        sortedRightHalf = mergeSort(L[i:])

        return _________________________________________