CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 9 (Due Thursday 26-Oct, at 10pm)



  1. Group Form [5 pts]:
    Fill out one form found here. This is due Thursday by 11:59pm. Even if you work on the lab alone (which you shouldn't do), you should still fill out the form, and simply enter your name without any partner scores.

    If you need a new group, fill out this form to be assigned to one.

  2. recursive alternatingSum(L) [15 pts] [autograded]
    Write the function alternatingSum(L) that takes a possibly-empty list of numbers, L, and returns their alternating sum, where every other value is subtracted rather than added. For example:
       alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3)
    If L is empty, return 0.

  3. recursive powersOf3ToN(n) [20 pts] [autograded]
    Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n, or None (not an empty list) if no such values exist. As an example, powersOf3ToN(10.5) returns [1, 3, 9].

  4. recursive binarySearchValues(L, v) [20 pts] [autograded]
    Write the 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.

  5. Book class [40 pts] [autograded]
    Write the Book class so that it passes testBookClass, and uses the OOP constructs we learned this week as appropriate.
    def testBookClass(): print("Testing Book class...", end="") # A Book has a title, and author, and a number of pages. # It also has a current page, which always starts at 1. There is no page 0! book1 = Book("Harry Potter and the Sorcerer's Stone", "J. K. Rowling", 309) assert(str(book1) == "Book<Harry Potter and the Sorcerer's Stone by " + "J. K. Rowling: 309 pages, currently on page 1>") book2 = Book("Carnegie Mellon Motto", "Andrew Carnegie", 1) assert(str(book2) == "Book<Carnegie Mellon Motto by Andrew Carnegie: " + "1 page, currently on page 1>") # You can turn pages in a book. Turning a positive number of pages moves # forward; turning a negative number moves backwards. You can't move past # the first page going backwards or the last page going forwards book1.turnPage(4) # turning pages does not return assert(book1.getCurrentPage() == 5) book1.turnPage(-1) assert(book1.getCurrentPage() == 4) book1.turnPage(400) assert(book1.getCurrentPage() == 309) assert(str(book1) == "Book<Harry Potter and the Sorcerer's Stone by " + "J. K. Rowling: 309 pages, currently on page 309>") book2.turnPage(-1) assert(book2.getCurrentPage() == 1) book2.turnPage(1) assert(book2.getCurrentPage() == 1) # You can also put a bookmark on the current page. This lets you turn # back to it easily. The book starts out without a bookmark. book3 = Book("The Name of the Wind", "Patrick Rothfuss", 662) assert(str(book3) == "Book<The Name of the Wind by Patrick Rothfuss: " + \ "662 pages, currently on page 1>") assert(book3.getBookmarkedPage() == None) book3.turnPage(9) book3.placeBookmark() # does not return assert(book3.getBookmarkedPage() == 10) book3.turnPage(7) assert(book3.getBookmarkedPage() == 10) assert(book3.getCurrentPage() == 17) assert(str(book3) == "Book<The Name of the Wind by Patrick Rothfuss: " + \ "662 pages, currently on page 17, page 10 bookmarked>") book3.turnToBookmark() assert(book3.getCurrentPage() == 10) book3.removeBookmark() assert(book3.getBookmarkedPage() == None) book3.turnPage(25) assert(book3.getCurrentPage() == 35) book3.turnToBookmark() # if there's no bookmark, don't turn to a page assert(book3.getCurrentPage() == 35) assert(str(book3) == "Book<The Name of the Wind by Patrick Rothfuss: " + \ "662 pages, currently on page 35>") # Finally, you should be able to compare two books directly book5 = Book("A Game of Thrones", "George R.R. Martin", 807) book6 = Book("A Game of Thrones", "George R.R. Martin", 807) book7 = Book("A Natural History of Dragons", "Marie Brennan", 334) book8 = Book("A Game of Spoofs", "George R.R. Martin", 807) assert(book5 == book6) assert(book5 != book7) assert(book5 != book8) book5.turnPage(1) assert(book5 != book6) book5.turnPage(-1) assert(book5 == book6) book6.placeBookmark() assert(book5 != book6) print("Done!")