Exercises for Lesson 22

Back to Lesson 22

Exercise 1: Bin packing

Consider the following set of activities, more generally labeled with letters as names:

    A: 2 hours
    B: 2 hours
    C: 2 hours
    D: 2 hours
    E: 3 hours
    F: 4 hours
    G: 5 hours

Part a: Three bins

Give a valid assignment of these activites to three bins, each of size 10.

Part b: Two bins

Give a valid assignment of these activities to two bins, each of size 10.

Part c: Complexity

What is the number of possible assignments of these seven activities to two bins, assuming we assign each activity to exactly one bin?

Back to Lesson 22

Exercise 2: The Activity class

We want to write an Activity class to represent the things we might do on the weekend. An Activity should be created with the following parameters:

  • name: a str
  • duration: an int representing the number of hours for this activity

Additionally, we want the following methods:

  • getName()
  • getDuration()

part a: Write the tests

Write a blank class definition (each method should have the right def line, but should just say pass).

class Activity:
    pass # TODO

Then write some tests to try out the functionality. This could be more complex with unittest, or just a simple example in a main function.

part b: Write the class

Complete the class definition. All of your tests should now pass.

part b: String representations

We can create a method to build a string representation of our Activity class. This method gets called when str() is used on an Activity object. Remember that as one of the special methods used with classes in Python, its name begins and ends with two underscores: __str__.

class Activity:
    ...

    def __str__(self):
        """
        Returns the string representation of this Activity.
        Example: "clean room (2 hours)"
        """
        return "" # TODO

Now we can print out the activities!

def main():
    # Hard-code a list of 8 activities
    activities = [Activity("clean room", 2),
                  Activity("cook meals", 3),
                  Activity("do homework", 3),
                  Activity("hang out with friends", 3),
                  Activity("eat", 1.5),
                  Activity("eat", 1.5),
                  Activity("eat", 1.5),
                  Activity("eat", 1.5)]

    # Print out the activities
    for activity in activities:
        print(activity) # calls Activity.__str__(activity)

part d: Another special method

We can create a method to allow us to add two Activity objects together, getting a composite Activity in return. This is another special method, so its name also begins and ends with two underscores: __add__. It is called when adding two Activity objects with +.

class Activity:
    ...

    def __add__(self, other):
        """
        Returns the combination of this Activity with another.
        The new Activity has:
          - name: concatenatation of both the names with ',' in between
          - duration: the sum of the two durations
        """
        return Activity("", 0) # TODO: replace with your code

Now we can combine activities!

def main():
    # Hard-code a list of 8 activities
    activities = [Activity("clean room", 2),
                  Activity("cook meals", 3),
                  Activity("do homework", 3),
                  Activity("hang out with friends", 3),
                  Activity("eat", 1.5),
                  Activity("eat", 1.5),
                  Activity("eat", 1.5),
                  Activity("eat", 1.5)]

    # Print out the activities
    for activity in activities:
        print(activity) # calls Activity.__str__(activity)

    # Add some together
    if len(activities) >= 3:
        a1 = activities[0]
        a2 = activities[1]
        a3 = activities[2]
        print(a1 + a2 + a3) # calls Activity.__add__(a1, a2) first

Back to Lesson 22