15-112
Spring-17

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

CMU 15-112 Spring 2017: Fundamentals of Programming and Computer Science
Homework 10 (Due Saturday 1-Apr, at 8pm)

  1. recursive isHappyNumber(n) [20 pts] [autograded]
    First, read about Happy Numbers here. After some thought, we see that no matter what number we start with, when we keep replacing the number by the sum of the squares of its digits, we'll always either arrive at 4 (unhappy) or at 1 (happy), and note that all numbers less than 1 are not happy. With that in mind, write the recursive function isHappyNumber(n) that returns True if n is happy and False otherwise. And to write that function, first write the recursive helper function sumOfSquaresOfDigits(n).

  2. recusive binarySearchValues(L, v) [20 pts] [autograded]
    Write the recursive function binarySearchValues(L, v) that takes a sorted list L and a value v and returns a list of tuples, (index, value), of the values that binary search must check to verify whether or not v is in L. As an example, say: 
       L = ['a', 'c', 'f', 'g', 'm', 'q']
   v = 'c'
    Binary search always searches between some lo and hi index, which initially are 0 and (len(L)-1). So here, lo=0 and hi=5. The first index we try, then, is mid=2 (the integer average of lo and hi). The value there is 'f', so we will add (2, 'f') to our result.

    Since 'f' is not the value we are seeking, we continue, only now we are searching from lo=0 to hi=1 (not hi=2 because we know that index 2 was too high!).

    Now we try mid=0 (the integer average of lo and hi), and so we add (0, 'a') to our result.

    We see that 'a' is too low, so we continue, only now with lo=1 and hi=1. So we add (1, 'c') to our result. We found 'c', so we're done. And so we see: 
        L = ['a', 'c', 'f', 'g', 'm', 'q']
    v = 'c'
    assert(binarySearchValues(L, v) == [(2,'f'), (0,'a'), (1,'c')])
    Hint: Do not slice the list L, but rather adjust the indexes into L.

  3. recursive evalPrefixNotation(L) [20 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 recursive 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 '*'. If you see any other operators, raise an exception as such: 
        raise Exception('Unknown operator: ' + operator)

    Hint: after removing the first element, if it is an operator, you should use evalPrefixNotation to recursively evaluate the operands for that operator.
    Take the time to really think about that hint! Also, for what it is worth, our sample solution used L.pop(0) to destructively remove the first element. We could then test if it was a string (and so an operator, like '+', or '-', etc) and do one thing, or if it is an int, and do something else.

  4. Polynomial class [40 pts] [autograded]
    Write the Polynomial class so that it passes testPolynomialClass, and uses the OOP constructs we learned this week as appropriate. Note that you are not required to use recursion in this class, and my use iteration if it helps.
    def testPolynomialClass(): print('Testing Polynomial class...', end='') testPolynomialBasics() testPolynomialEq() testPolynomialConstructor() testPolynomialInSets() print('Passed.') def testPolynomialBasics(): # we'll use a very simple str format... assert(str(Polynomial([1,2,3])) == "Polynomial(coeffs=[1, 2, 3])") p1 = Polynomial([2, -3, 5]) # 2x**2 -3x + 5 assert(p1.degree() == 2) # p.coeff(i) returns the coefficient for x**i assert(p1.coeff(0) == 5) assert(p1.coeff(1) == -3) assert(p1.coeff(2) == 2) # p.evalAt(x) returns the polynomial evaluated at that value of x assert(p1.evalAt(0) == 5) assert(p1.evalAt(2) == 7) # p.scaled(scale) returns a new polynomial with all the # coefficients multiplied by the given scale p2 = p1.scaled(10) # 20x**2 - 30x + 50 assert(isinstance(p2, Polynomial)) assert(p2.evalAt(0) == 50) assert(p2.evalAt(2) == 70) def testPolynomialEq(): assert(Polynomial([1,2,3]) == Polynomial([1,2,3])) assert(Polynomial([1,2,3]) != Polynomial([1,2,3,0])) assert(Polynomial([1,2,3]) != Polynomial([1,2,0,3])) assert(Polynomial([1,2,3]) != Polynomial([1,-2,3])) assert(Polynomial([1,2,3]) != 42) assert(Polynomial([1,2,3]) != "Wahoo!") # A polynomial of degree 0 has to equal the same non-Polynomial numeric! assert(Polynomial([42]) == 42) def testPolynomialConstructor(): # If the list is empty, treat it the same as [0] assert(Polynomial([]) == Polynomial([0])) assert(Polynomial([]) != Polynomial([1])) # Remove leading 0's assert(Polynomial([0,0,0,1,2]) == Polynomial([1,2])) assert(Polynomial([0,0,0,1,2]).degree() == 1) # Require that the constructor be non-destructive coeffs = [0,0,0,1,2] assert(Polynomial(coeffs) == Polynomial([1,2])) assert(coeffs == [0,0,0,1,2]) # Require that the constructor also accept tuples of coefficients coeffs = (0, 0, 0, 1, 2) assert(Polynomial(coeffs) == Polynomial([1,2])) def testPolynomialInSets(): s = set() assert(Polynomial([1,2,3]) not in s) s.add(Polynomial([1,2,3])) assert(Polynomial([1,2,3]) in s) assert(Polynomial([1,2,3]) in s) assert(Polynomial([1,2]) not in s)

  5. Optional/Bonus: recursiveTetris() [5 pts] [manually graded]
    Below the #ignore_rest line, write the function recursiveTetris() that takes no arguments and when called plays Tetris, though of course without any iteration in the implementation. Have fun!