15-112
Fall-17

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Homework 9 (Due Saturday, 28-Oct, at 8pm)

  1. Take the midsemester course survey [10 pts] [manually graded]
    The survey is now available: you can find it here!
    We want your feedback on how the course is going, so we can keep trying to make it better. Therefore, we'd like you to answer some questions!
    Note: this survey will be anonymous. When you complete the survey, you'll get a link to a different form where you can enter your andrewID to receive the homework credit. We will not be able to map your survey response to your andrewID.

  2. recursive powerSum(n, k) [10 pts] [autograded]
    Write the function powerSum(n, k) that takes two possibly-negative integers n and k and returns the so-called power sum:
       1**k + 2**k + ... + n**k
    If n is negative, return 0. Similarly, if k is negative, return 0.

  3. recursive isHappyNumber(n) [15 pts] [autograded]
    Write the function isHappyNumber from Hw2, but recursively. Note that you'll probably need to reimplement sumOfSquaresOfDigits as well...

  4. recursive evalPrefixNotation(L) [15 pts] [autograded]
    Background: in so-called 'prefix notation', an arithmetic expression is listed with the operator first. So instead of writing '2 + 3' we would write '+ 2 3'. Actually, for this problem, we'll represent the expression in a list, so we'd write ['+', 2, 3]. Each value can itself be another full expression, so for example we could have: 
        ['+', 2, '*', 3, 4]
    This would be the same as (2 + (3 * 4)), or 14. Again, we could have: 
        ['+', '*', 2, 3, '*', 4, 5]
    This would be the same as ((2 * 3) + (4 * 5)), or 26. Look at the test function in the code for a few more examples.

    With this in mind, write the function evalPrefixNotation(L) that takes a list L that contains a legal arithmetic expression in prefix notation, as just described, and returns the value that the expression evaluates to.

    Your function only needs to work for '+', '-', and '*'.
    Hint: this problem becomes drastically easier if you implement it destructively. Our sample solution used L.pop(0) to get the first element, for example. Evaluating the operands then becomes much simpler...

  5. VendingMachine class [50 pts] [autograded]
    Write the VendingMachine class so that it passes testVendingMachineClass, and uses the OOP constructs we learned this week as appropriate.
    Hint: Make sure you're representing money properly wherever it might appear in the string representation of a Vending Machine. The test cases shown here don't cover every possible case...
    def testVendingMachineClass(): print("Testing Vending Machine class...", end="") # Vending machines have three main properties: # how many bottles they contain, the price of a bottle, and # how much money has been paid. A new vending machine starts with no # money paid. vm1 = VendingMachine(100, 125) assert(str(vm1) == "Vending Machine:<100 bottles; $1.25 each; $0 paid>") assert(vm1.isEmpty() == False) assert(vm1.getBottleCount() == 100) assert(vm1.stillOwe() == 125) # When the user inserts money, the machine returns a message about their # status and any change they need as a tuple. assert(vm1.insertMoney(20) == ("Still owe $1.05", 0)) assert(vm1.stillOwe() == 105) assert(vm1.getBottleCount() == 100) assert(vm1.insertMoney(5) == ("Still owe $1", 0)) # When the user has paid enough money, they get a bottle and # the money owed resets. assert(vm1.insertMoney(100) == ("Got a bottle!", 0)) assert(vm1.getBottleCount() == 99) assert(vm1.stillOwe() == 125) assert(str(vm1) == "Vending Machine:<99 bottles; $1.25 each; $0 paid>") # If the user pays too much money, they get their change back with the # bottle. assert(vm1.insertMoney(500) == ("Got a bottle!", 375)) assert(vm1.getBottleCount() == 98) assert(vm1.stillOwe() == 125) # Machines can become empty vm2 = VendingMachine(1, 120) assert(str(vm2) == "Vending Machine:<1 bottle; $1.20 each; $0 paid>") assert(vm2.isEmpty() == False) assert(vm2.insertMoney(120) == ("Got a bottle!", 0)) assert(vm2.getBottleCount() == 0) assert(vm2.isEmpty() == True) # Once a machine is empty, it should not accept money until it is restocked. assert(str(vm2) == "Vending Machine:<0 bottles; $1.20 each; $0 paid>") assert(vm2.insertMoney(25) == ("Machine is empty", 25)) assert(vm2.insertMoney(120) == ("Machine is empty", 120)) assert(vm2.stillOwe() == 120) vm2.stockMachine(20) # Does not return anything assert(vm2.getBottleCount() == 20) assert(vm2.isEmpty() == False) assert(str(vm2) == "Vending Machine:<20 bottles; $1.20 each; $0 paid>") assert(vm2.insertMoney(25) == ("Still owe $0.95", 0)) assert(vm2.stillOwe() == 95) vm2.stockMachine(20) assert(vm2.getBottleCount() == 40) # We should be able to test machines for basic functionality vm3 = VendingMachine(50, 100) vm4 = VendingMachine(50, 100) vm5 = VendingMachine(20, 100) vm6 = VendingMachine(50, 200) vm7 = "Vending Machine" assert(vm3 == vm4) assert(vm3 != vm5) assert(vm3 != vm6) assert(vm3 != vm7) # should not crash! s = set() assert(vm3 not in s) s.add(vm4) assert(vm3 in s) s.remove(vm4) assert(vm3 not in s) assert(vm4.insertMoney(50) == ("Still owe $0.50", 0)) assert(vm3 != vm4) print("Done!")