Lab 12: Final Review (Optional)

Starter Files

Download lab12.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

This lab assignment is OPTIONAL. This means it does not count toward your final grade, and completing it will NOT earn you any extra credit. It is intended to help with studying for the final exam. Note that the topics listed in this lab are NOT comprehensive of the scope of the final.

You do not have to submit to Gradescope, although there is an assignment with the autograder if you want to check your work.

Solutions are available here.

Control

Question 1: Second Max

Write a function that finds the second highest number in a list of positive integers. You can assume that the list always has at least two integers.

def second_max(lst):
    """ 
    Return the second highest number in a list of positive integers.

    >>> second_max([3, 2, 1, 0])
    2
    >>> second_max([2, 3, 3, 4, 5, 6, 7, 2, 3])
    6
    >>> second_max([1, 5, 5, 5, 1])
    5
    >>> second_max([5, 6, 6, 7, 1])
    6
    >>> second_max([5, 6, 7, 7, 1])
    7
    """

    "*** YOUR CODE HERE ***"
    highest = 0
    second_highest = 0
    for num in lst:
        if num >= highest:
            second_highest = highest
            highest = num
        elif num < highest and num > second_highest:
            second_highest = num
    return second_highest

Use OK to test your code:

python3 ok -q second_max

Higher Order Functions

Question 2: Count van Count

Consider the following implementations of count_factors and count_primes:

def count_factors(n):
    """Return the number of positive factors that n has."""
    i, count = 1, 0
    while i <= n:
        if n % i == 0:
            count += 1
        i += 1
    return count

def count_primes(n):
    """Return the number of prime numbers up to and including n."""
    i, count = 1, 0
    while i <= n:
        if is_prime(i):
            count += 1
        i += 1
    return count

def is_prime(n):
    return count_factors(n) == 2 # only factors are 1 and n

The implementations look quite similar! Generalize this logic by writing a function count_cond, which takes in a two-argument predicate function mystery_function(n, i). count_cond returns a count of all the numbers from 1 to n that satisfy mystery_function.

Note: A predicate function is a function that returns a boolean (True or False).

def count_cond(mystery_function, n):
    """
    >>> def divisible(n, i):
    ...     return n % i == 0
    >>> count_cond(divisible, 2) # 1, 2
    2
    >>> count_cond(divisible, 4) # 1, 2, 4
    3
    >>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
    6

    >>> def is_prime(n, i):
    ...     return count_cond(divisible, i) == 2
    >>> count_cond(is_prime, 2) # 2
    1
    >>> count_cond(is_prime, 3) # 2, 3
    2
    >>> count_cond(is_prime, 4) # 2, 3
    2
    >>> count_cond(is_prime, 5) # 2, 3, 5
    3
    >>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    "*** YOUR CODE HERE ***"
    
    i, count = 1, 0
    while i <= n:
        if mystery_function(n, i):
            count += 1
        i += 1
    return count

Use OK to test your code:

python3 ok -q count_cond

Lists and Dictionaries

Question 3: Deep-Len

A list that contains one or more lists as elements is called a deep list. For example, [1, [2, 3], 4] is a deep list.

Write a function deep_len that takes a list and returns its deep length. See the doctests for the function's behavior.

Hint: you can check if something is a list by using the built-in type function. For example,

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

def deep_len(lst):
    """Returns the deep length of the list.

    >>> deep_len([1, 2, 3])     # normal list
    3
    >>> x = [1, [2, 3], 4]      # deep list
    >>> deep_len(x)
    4
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> deep_len(x)
    6
    """
    "*** YOUR CODE HERE ***"
    if not lst:
        return 0
    elif type(lst[0]) == list:
        return deep_len(lst[0]) + deep_len(lst[1:])
    else:
        return 1 + deep_len(lst[1:])

Use OK to test your code:

python3 ok -q deep_len

Question 4: Counter

Implement the function counter which takes in a string of words message, and returns a dictionary where each key is a word in the message, and each value is the number of times that word is present in the original string.

def counter(message):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input string.

    >>> x = counter('to be or not to be')
    >>> x['to']
    2
    >>> x['be']
    2
    >>> x['not']
    1
    >>> y = counter('run forrest run')
    >>> y['run']
    2
    >>> y['forrest']
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
    
    result_dict = {}
    for word in word_list:
        if word in result_dict:
            result_dict[word] += 1
        else:
            result_dict[word] = 1
    return result_dict

Use OK to test your code:

python3 ok -q counter

Recursion

Question 5: Knapsack

You're are a thief, and your job is to pick among n items that are of different weights and values. You have a knapsack that supports c pounds, and you want to pick some subset of the items so that you maximize the value you've stolen.

Define knapsack, which takes a list weights, list values and a capacity c, and returns that max value. You may assume that item 0 weighs weights[0] pounds, and is worth values[0]; item 1 weighs weights[1] pounds, and is worth values[1]; etc.

def knapsack(weights, values, c):
    """
    >>> w = [2, 6, 3, 3]
    >>> v = [1, 5, 3, 3]
    >>> knapsack(w, v, 6)
    6
    """
    "*** YOUR CODE HERE ***"
    if weights == []:
        return 0
    else:
        first_weight, rest_weights = weights[0], weights[1:]
        first_value, rest_values = values[0], values[1:]
        with_first = first_value + knapsack(rest_weights, rest_values, c - first_weight)
        without_first = knapsack(rest_weights, rest_values, c)
        if first_weight <= c:
            return max(with_first, without_first)
        return without_first

Use OK to test your code:

python3 ok -q knapsack

Question 6: repeated, repeated

In Homework 2 you encountered the repeated function, which takes arguments f and n and returns a function equivalent to the nth repeated application of f. This time, we want to write repeated recursively. You'll want to use compose1, given below for your convenience:

def compose1(f, g):
    """"Return a function h, such that h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

def repeated(f, n):
    """
    >>> f = lambda x: x + 1
    >>> g = repeated(f, 1)
    >>> g(5)
    6
    >>> h = repeated(f, 3)
    >>> h(5)
    8
    >>> f2 = lambda x: x * 2
    >>> g2 = repeated(f2, 3)
    >>> g2(3)
    24
    """
    "*** YOUR CODE HERE ***"
    if n == 0:
        return lambda x: x # Identity 
    return compose1(f, repeated(f, n - 1))

Use OK to test your code:

python3 ok -q repeated

OOP and Inheritance

Question 7: Mint

Complete the Mint and Coin classes so that the coins created by a mint have the correct year and worth.

Each Mint instance has a year stamp. The update method sets the year stamp to the current_year class attribute of the Mint class.
The create method takes a subclass of Coin and returns an instance of that class stamped with the mint's year (which may be different from Mint.current_year if it has not been updated.) Hint: Check out the create_animal method in this demo.
A Coin's worth method returns the cents value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the current_year class attribute of the Mint class.

class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.current_year.

    >>> mint = Mint()
    >>> mint.year
    2020
    >>> dime = mint.create(Dime)
    >>> dime.year
    2020
    >>> Mint.current_year = 2100  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2020
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2100
    >>> Mint.current_year = 2175     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years). 155 is because this dime instance has year 2020
    115
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    125
    >>> m = Mint()
    >>> n = m.create(Nickel)
    >>> n.worth()
    5
    >>> n.year = 2015
    >>> n.worth() # 5 cents + (160 - 50 years). 160 is from 2175 - 2015
    115
    """
    current_year = 2020

    def __init__(self):
        self.update()

    def create(self, coin):
        "*** YOUR CODE HERE ***"
        return coin(self.year)
    def update(self):
        "*** YOUR CODE HERE ***"
        self.year = Mint.current_year
class Coin:
    cents = 0 # Default value of 0. This value will be overridden in subclasses.

    def __init__(self, year):
        self.year = year

    def worth(self):
        "The worth is a coin's face value + 1 cent for each year over age 50."
        "*** YOUR CODE HERE ***"
        return self.cents + max(0, Mint.current_year - self.year - 50)
class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

Use OK to test your code:

python3 ok -q Mint

Linked Lists

Question 8: Insert

Implement a function insert that takes a Link, a value, and an index, and inserts the value into the Link at the given index. You can assume the linked list already has at least one element. Do not return anything — insert should mutate the linked list.

Note: If the index is out of bounds, you can raise an IndexError with:
raise IndexError

def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> print_link(link)
    <1 2 3>
    >>> insert(link, 9001, 0)
    >>> print_link(link)
    <9001 1 2 3>
    >>> insert(link, 100, 2)
    >>> print_link(link)
    <9001 1 100 2 3>
    >>> insert(link, 4, 5)
    IndexError
    """
    "*** YOUR CODE HERE ***"
    if index == 0:
        link.rest = Link(link.first, link.rest)
        link.first = value
    elif link.rest is Link.empty:
        raise IndexError
    else:
        insert(link.rest, value, index - 1)

# iterative solution
def insert(link, value, index):
    while index > 0 and link.rest is not Link.empty:
        link = link.rest
        index -= 1
    if index == 0:
        link.rest = Link(link.first, link.rest)
        link.first = value
    else:
        raise IndexError

Use OK to test your code:

python3 ok -q insert

Trees

Question 9: Path

Write a function path that returns the path from the root of the tree to the given value target as a list if it exists and [] if it does not. You can assume all values are unique.

def path(t, target):
    """
    >>> t = Tree(9, [Tree(7, [Tree(3), Tree(2)]), Tree(5)])
    >>> path(t, 2)
    [9, 7, 2]
    >>> path(t, 5)
    [9, 5]
    >>> path(t, 8)
    []
    """
    "*** YOUR CODE HERE ***"
    if t.value == target:
        return [target]
    elif t.is_leaf():
        return []
    else:
        for b in t.branches:
            rest = path(b, target)
            if rest:
                return [t.value] + rest
        return []

Use OK to test your code:

python3 ok -q path

Iterators and Generators

Question 10: Str

Write an iterator that takes a string as input and outputs the letters in order when iterated over.

class Str:
    def __init__(self, str):
        self.str = str
    def __iter__(self):
        return iter(self.str)

That works (why?), but just kidding.

class Str:
    """
    >>> hey_iter = Str('hey')
    >>> for char in hey_iter:
    ...     print(char)
    h
    e
    y
    >>> list(hey_iter)
    []
    """
    def __init__(self, str):
        "*** YOUR CODE HERE ***"
        self.str = str
        self.i = -1
    def __iter__(self):
        "*** YOUR CODE HERE ***"
        return self
    def __next__(self):
        "*** YOUR CODE HERE ***"
        self.i += 1
        if self.i >= len(self.str):
            raise StopIteration
        return self.str[self.i]

Use OK to test your code:

python3 ok -q Str

Question 11: Generate permutations

Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, [2, 1, 3], [1, 3, 2], and [3, 2, 1] are all permutations of the list [1, 2, 3].

Implement generate_perms, a generator function which takes in a lst and yields all the unique permutations of lst one at a time (see doctest for examples).

def generate_perms(lst):
    """
    Generates the permutations of lst one by one.
    >>> perms = generate_perms([1, 2, 3])
    >>> hasattr(perms, '__next__')
    True
    >>> p = list(perms)
    >>> p.sort()
    >>> p
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """
    if lst == []:
        "*** YOUR CODE HERE ***"
        yield []    else:
        for perm in generate_perms(lst[1:]):
            for i in range(len(lst)):
                "*** YOUR CODE HERE ***"
                yield perm[:i] + [lst[0]] + perm[i:]

Use OK to test your code:

python3 ok -q generate_perms

Feel free to replace the for loops with list comprehensions if you would rather use that.

Efficiency

There is no code to submit for this part.

Question 12

What is the asymptotic run time of the baz function?

def baz(n):
    i = 1
    sum = 0
    while i <= n:
        sum += bam(i)
        i += 1
    return sum

def bam(n):
    i = 1
    sum = 0
    while i <= n:
        sum += i
        i += 1
    return sum

Highlight the text on the line below this line to see the solution:
Answer: O(n²)).

Question 13

What is the asymptotic run time of the bonk function?

def bonk(n):
    sum = 0
    while n >= 2:
        sum += n
        n = n / 2
    return sum

Highlight the text on the line below this line to see the solution:
Answer: O(log(n)).

Submission

When you are done, submit your file to Gradescope. You only need to upload the following files:

lab12.py

You may submit more than once before the deadline; only the final submission will be graded. It is your responsibility to check that the autograder on Gradescope runs as expected after you upload your submission.

Lab 12: Final Review (Optional) Due at 11:59:59 pm on 5/10/2024.

Starter Files

Control

Question 1: Second Max

Higher Order Functions

Question 2: Count van Count

Lists and Dictionaries

Question 3: Deep-Len

Question 4: Counter

Recursion

Question 5: Knapsack

Question 6: repeated, repeated

OOP and Inheritance

Question 7: Mint

Linked Lists

Question 8: Insert

Trees

Question 9: Path

Iterators and Generators

Question 10: Str

Question 11: Generate permutations

Efficiency

Question 12

Question 13

Submission

Lab 12: Final Review (Optional)
Due at 11:59:59 pm on 5/10/2024.