Homework 8
Due at 11:59:59 pm on Thursday, 4/7/2022.

hw08.zip

Instructions

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

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org.

Readings: This homework relies on following references:

Recall that the order of growth of a function expresses how long it takes for the function to run, and is defined in terms of the function's input sizes.

For example, let's say that we have the function get_x which is defined as follows:

def get_x(x):
    return x

get_x has one expression in it. That one expression takes the same amount of time to run, no matter what x is, or more importantly, how large x gets. This is called constant time, or O(1).

The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!

The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:

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

This loop has one statement in it sum, i = sum + i, i + 1. This statement is considered to run in constant time, as none of its operations rely on the size of the input. Individually, sum = sum + 1 and i = i + 1 are both constant time operations. However, when we're looking at order of growth, we don't add the times together and get O(2), we take the maximum of those 2 values and use that as the running time. In 61A, we are not concerned with how long primitive functions, such as addition, multiplication, and variable assignment, take in order to run - we are mainly concerned with how many more times a loop is executed or how many more recursive calls occur as the input increases. In this example, we execute the loop n times, and for each iteration, we only execute constant time operations, so we get an order of growth of O(n).

Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.

  1. O(n)

    def bar(n):
    i, a, b = 1, 1, 0
    while i <= n:
        a, b, i = a + b, a, i + 1
     return a

  2. O(n^2)

    def bar(n):
    sum = 0
    a, b = 0, 0
    while a < n:
        while b < n:
            sum += (a*b)
            b += 1
        b = 0
        a += 1
    return sum

Efficiency

There is nothing to submit for this part. But doing these problems will be good practice. The solutions are given right below the question. Try covering the solution and see if you can solve the them!

For each question find the asymptotic runtime in big theta notation.

Question 1

What is the asymptotic run time of the baz function.

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

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

O(n2)

Question 2

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

O(log(n))

Question 3

This question is very challenging. This is much beyond what we expect you to know for the exam. This is here merely to challenge you.

def boink(n):
    if n == 1:
        return 1
    value = 0
    i = 0
    while i < n:
        value += boink(i)
        i += 1
    return value
Exponential, e.g. O(2n)

Inheritance

Question 4: Errors

It is often said that nothing in life is certain but death and taxes. For a programmer or data scientist, however, nothing is certain but encountering errors.

In Python, there are two primary types of errors, both of which you are likely familiar with: syntax errors and exceptions. Syntax errors occur when the proper structure of the language is not followed, while exceptions are errors that occur during the execution of a program. These include errors such as ZeroDivisionError, TypeError, NameError, and many more!

Under the hood, these errors are based in the concepts of object orientation, and all exceptions are class objects. If you're interested in more detailed explanations of the structure of exceptions as well as how to create your own, check out this article from the Python documentation! In the meantime, we'll implement our own version of an Error class

Complete the Error, SyntaxError, and ZeroDivisionError classes such that they create the correct messages when called.

  • The SyntaxError and ZeroDivisionError classes inherit from the Error class and add functionality that is unique to those particular errors. Their code is partially implemented for you.
  • The add_code method adds a new helpful message to your error, while the write method should print the output that you see when an error is raised.
  • You can access the parent class methods using the super() function
class Error:
    """
    >>> err1 = Error(12, "error.py")
    >>> err1.write()
    error.py:12
    """
    def __init__(self, line, file):
        "*** YOUR CODE HERE ***"

    def format(self):
        return self.file + ':' + str(self.line)

    def write(self):
        print(self.format())

class SyntaxError(Error):
    """
    >>> err1 = SyntaxError(17, "lab10.py")
    >>> err1.write()
    lab10.py:17 SyntaxError : Invalid syntax
    >>> err1.add_code(4, "EOL while scanning string literal")
    >>> err2 = SyntaxError(18, "lab10.py", 4)
    >>> err2.write()
    lab10.py:18 SyntaxError : EOL while scanning string literal
    """
    type = 'SyntaxError'
    msgs = {0 : "Invalid syntax", 1: "Unmatched parentheses", 2: "Incorrect indentation", 3: "missing colon"}

    def __init__(self, line, file, code=0):
        "*** YOUR CODE HERE ***"

    def format(self):
        "*** YOUR CODE HERE ***"

    def add_code(self, code, msg):
        "*** YOUR CODE HERE ***"

class ZeroDivisionError(Error):
    """
    >>> err1 = ZeroDivisionError(273, "lab10.py")
    >>> err1.write()
    lab10.py:273 ZeroDivisionError : division by zero
    """
    type = 'ZeroDivisionError'

    def __init__(self, line, file, message='division by zero'):
        "*** YOUR CODE HERE ***"

    def format(self):
        end = self.type + ' : ' + self.message
        "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q Error

Use OK to test your code:

python3 ok -q SyntaxError

Use OK to test your code:

python3 ok -q ZeroDivisionError

Question 5: Checking account

We'd like to be able to cash checks, so let's add a deposit_check method to our CheckingAccount class. It will take a Check object as an argument, and check to see if the payable_to attribute matches the CheckingAccount's holder. If so, it marks the Check as deposited, and adds the amount specified to the CheckingAccount's total.

Write an appropriate Check class, and add the deposit_check method to the CheckingAccount class. Make sure not to copy and paste code! Use inheritance whenever possible.

See the doctests for examples of how this code should work.

The Account class has been provided.

class Account(object):
    """A bank account that allows deposits and withdrawals.

    >>> eric_account = Account('Eric')
    >>> eric_account.deposit(1000000)   # depositing my paycheck for the week
    1000000
    >>> eric_account.transactions
    [('deposit', 1000000)]
    >>> eric_account.withdraw(100)      # buying dinner
    999900
    >>> eric_account.transactions
    [('deposit', 1000000), ('withdraw', 100)]
    """

    interest = 0.02

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder
        self.transactions = []

    def deposit(self, amount):
        """Increase the account balance by amount and return the
        new balance.
        """
        self.transactions.append(('deposit', amount))
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        """Decrease the account balance by amount and return the
        new balance.
        """
        self.transactions.append(('withdraw', amount))
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance

class CheckingAccount(Account):
    """A bank account that charges for withdrawals.

    >>> check = Check("Steven", 42)  # 42 dollars, payable to Steven
    >>> steven_account = CheckingAccount("Steven")
    >>> eric_account = CheckingAccount("Eric")
    >>> eric_account.deposit_check(check)  # trying to steal steven's money
    The police have been notified.
    >>> eric_account.balance
    0
    >>> check.deposited
    False
    >>> steven_account.balance
    0
    >>> steven_account.deposit_check(check)
    42
    >>> check.deposited
    True
    >>> steven_account.deposit_check(check)  # can't cash check twice
    The police have been notified.
    """
    withdraw_fee = 1
    interest = 0.01

    def withdraw(self, amount):
        return Account.withdraw(self, amount + self.withdraw_fee)



class Check(object):
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q CheckingAccount

Submit

Make sure to submit this assignment by running:

python3 ok --submit