Recitation 4: Loop Invariants

For the following functions, consider:

Function One

def maximum(a_list):
    maximum = float('-inf')
    i = 0
    # What is the precondition?
    # Invariant
    while i < len(a_list):
        # Invariant
        if a_list[i] > maximum:
            maximum = a_list[i]
        i += 1
        # Invariant
    # Invariant
    # What is the postcondition?
    return maximum

Function Two

def maximum2(a_list):
    maximum = float('-inf')

    # What is the precondition?
    # Invariant
    for element in a_list:
        # Invariant
        if element > maximum:
            maximum = element
        # Invariant
    # Invariant
    # What is the postcondition?
    return maximum

Function Three

This is probably not the best way to implement this function. Once you’ve determined the loop invariant for this implementation,

def nested_maximum(a_list_of_lists):
    maximum = float('-inf')

    for a_list in a_list_of_lists:
        temp_max = float('-inf')

        for element in a_list:
            if element > temp_max:
                temp_max = element
        if temp_max > maximum:
            maximum = temp_max

    return maximum

Function Four

def factorial(n):
    fact = 1

    for i in range(1, n+1):
        fact = fact*i

    return fact

Function Five

def powers_of_two(n):
    total = 1
    i = 0

    while i < n:
        total += 2**i # Exponentiation
        i += 1

    return total

Function Six

def reverse(n):
    m = n
    rever = 0

    while m > 0:
        remainder = m % 10
        rever = 10*rever + remainder
        m = m // 10 # Integer division (the floor of m/10)

    return rever

Function Seven

def bubble_sort(a_list):
    for passes in range(len(a_list)-1, 0, -1):
        for i in range(passes):
            if a_list[i] > a_list[i + 1]:
                a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i] # This swaps two values
    return a_list

Challenge problem:

Nim: Given two piles of counters, each having an arbitrary number of initial counters. Two players take turns removing counters from the piles. Each player chooses to remove as many counters as they would like (but at least one). The player who removes the last counter wins the game.