Due at 11:59:59 pm on Friday, 11/13/2020.
Download hw09.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. See this article for more instructions on okpy and submitting assignments.
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.
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.
def bar(n): i, a, b = 1, 1, 0 while i <= n: a, b, i = a + b, a, i + 1 return a
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
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.
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
def bonk(n): sum = 0 while n >= 2: sum += n n = n / 2 return sum
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 sum = 0 i = 1 while i <= n: sum += boink(i) i += 1 return sum
Question 4: Mint
Coin classes so that the coins created by a mint have
the correct year and worth.
Mintinstance has a
updatemethod sets the
yearstamp to the
current_yearclass attribute of the
createmethod takes a subclass of
Coinand returns an instance of that class stamped with the
mint's year (which may be different from
Mint.current_yearif it has not been updated.)
worthmethod returns the
centsvalue 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_yearclass attribute of the
Use OK to test your code:
python3 ok -q Mint
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) 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() 115 """ current_year = 2020 def __init__(self): self.update() def create(self, kind): "*** YOUR CODE HERE ***" def update(self): "*** YOUR CODE HERE ***" class Coin: 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 ***" class Nickel(Coin): cents = 5 class Dime(Coin): cents = 10
Question 5: Checking account
We'd like to be able to cash checks, so let's add a
method to our
CheckingAccount class. It will take a
as an argument, and check to see if the
payable_to attribute matches
CheckingAccount's holder. If so, it marks the
deposited, and adds the amount specified to the
Write an appropriate
Check class, and add 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.
Account class has been provided.
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