Quiz 6 Study Guide

Quiz 6 will go live on May 7 and be available until midnight on May 12. You will have one hour to complete the quiz. You are welcome to consult your class notes and any previous code that you wrote for class, however you may not get any outside help or search the internet for assistance. You will start the quiz by logging on to the CS machines and typing quiz21 in a terminal window.

The CS21 staff will continue to be available on Slack at the following
dates and times to help you prepare for the quiz:

* Monday, May 4 2:00 - 4:00 pm
* Tuesday, May 5 10:00 - 11:00 am and during normal lab times
* Wednesday, May 6 during normal lab times

Quiz Study Guides are provided as a courtesy. You may work with other students on the questions, and ask questions about the guide during evening ninja help sessions, on slack, or during meetings with faculty and staff. We do not provide full solutions to the quiz guides.

You are responsible for all material covered through the end of Week 13.

This quiz will focus on the following:

Python concepts

  • Writing recursive functions

  • Defining your own classes

You should be able to

  • Compare and contrast iterative and recursive solutions to the same problem

  • Use classes to solve problems

Practice problems on recursion

  1. Write a recursive function called blastoff that takes a positive integer and counts down (printing one number per line) from the given starting number to 1. For example, blastoff(5) would print:

5
4
3
2
1
blast off!

  1. Write a recursive function called headsInFlips that takes a positive integer and simulates flipping a coin that many times. It should return the number of heads. For example, headsInFlips(100) might return 50 (or 48, or 51, etc.).

  2. Write a recursive function called fixListRecur that takes a list of numbers and two integers that bound the values that the list may contain. It builds up a new list where any out of bound values are dropped from the list (you may not use the list remove function to accomplish this). For example:

    • fixListRecur([9, -1, 0, 12, 10, 4], 0, 10) should return [9, 0, 10, 4]

    • fixListRecur([22, 24, 26], 20, 30) should return [22, 24, 26]

  3. Write an iterative function called fixListIter that does the same task as the previous problem but instead of recursion uses a loop. For example:

    • fixListIter([9, -1, 0, 12, 10, 4], 0, 10) should return [9, 0, 10, 4]

    • fixListIter([22, 24, 26], 20, 30) should return [22, 24, 26]

  4. In terms of the stack, what is different in how the computer will execute the recursive vs the iterative solution?

If you aren’t sure how to answer the previous question, you may want to use the python tutor to visualize their execution.

Practice problems on classes

  1. Consider the Pizza class defined below.

    • What data does every Pizza object store?

    • Which method is known as the constructor?

    • What does self represent?

    • Do you need to explicitly pass a value into self when you call a method?

class Pizza(object):
    def __init__(self, size):
        assert(size == "small" or size == "large")
        self.size = size
        self.toppings = []
    def __str__(self):
        result = "Pizza: " + self.size + " with "
        if len(self.toppings) == 0:
            result += "no toppings"
        else:
            for i in range(len(self.toppings)):
                result += self.toppings[i] + " "
        return result
    def addTopping(self, item):
        self.toppings.append(item)
    def getCost(self):
        if self.size == "small":
            cost = 10 + .5 * len(self.toppings)
        else:
            cost = 12 + .75 * len(self.toppings)
        return cost

  1. Now consider the main program shown below that uses the Pizza class.

    • What method of the Pizza class will be called in lines 2 and 7?

    • What method of the Pizza class will be called in lines 5 and 10?

1  def main():
2     veggie = Pizza("small")
3     veggie.addTopping("spinach")
4     veggie.addTopping("peppers")
5     print(veggie)
6     print("Cost: $%.2f" % veggie.getCost())
7     meatlovers = Pizza("large")
8     meatlovers.addTopping("pepperoni")
9     meatlovers.addTopping("sausage")
10    print(meatlovers)
11    print("Cost: $%.2f" % meatlovers.getCost())

12 main()

  1. Write a Book class to represent information about books. This class should store data on the title and the author of the book. It should also keep track of the current edition, which by default should always start at 1. Write the following methods:

    • The constructor should take the title and the author as parameters.

    • The special string method should print a nicely formatted string that includes the title, author, and the current edition.

    • Include getter methods for the title, author, and edition.

    • Since the title and author are unlikely to change, just include a setter method called updateEdition that increments the current edition number by 1.

  1. Write a main program to test your Book class. You should create several books and add unit tests to verify that all of the methods are working as you expect them to.