Homework 5¶

Due Tuesday, November 9th 2021 at 11:59 PM.¶

Problem 0. Homework Workflow [10 pts]

Problem 1. @property Decorator [35 pts]

Problem 2. Binary Search Tree [55 pts]

We will be using an autograder for this homework. Please don't change the specified function signature.

Problem 0: Homework Workflow¶

Once you receive HW4 feedback, you will need to merge your HW4-dev branch into master.

You will earn points for following all stages of the git workflow which involves:

• 3pts for merging HW4-dev into master
• 5pts for completing HW5 on HW5-dev
• 2pts for making a PR on HW5-dev to merge into master

Problem 1: @property Decorator¶

Suppose we have a simple Animal class, which is initialized by its species:

class Animal:

    def __init__(self, name, species):
        self.name = name
        self.species = species

    def __repr__(self):
        return f'{self.name} ({self.species})'

We have clients who build applications on top of our Animal class and they want to directly modify the species attribute. For example, they may implement functions to transform animals.

def transform(animal, into):
    animal.species = into
    return animal

However, one day it occurred to us that our Animal class is designed to be used in an H. C. Andersen universe. We really don't want people to make an Animal instance into a Cthulhu [Cthulhu is not part of the H. C. Anderson universe]. How should we enforce this restriction? The obvious solution is to create a method to set the species, which checks if the new species is valid inside the method:

class Animal:

    # a class attribute of the valid species in our universe
    valid_species = {
        'cat',
        'dog',
        'duck',
        'elf',
        'goblin',
        'horse',
        'human',
        'mermaid',
        'nightingale',
        'pig',
        'swan',
        'wolf'
    }

    def __init__(self, species):
        self.species = species

    def __repr__(self):
        return f'{self.name} ({self.species})'

    def set_species(self, into):
        assert into in Animal.valid_species, Exception(f'invalid species: {into}')
        self.species = into

There are two problems with this implementation:

1. If our clients don't know they have to change their implementation of transform (use set_species instead of directly assign the species attribute), people can still do things like a = transform(ugly_duckling, into='Cthulhu')
2. We really don't want to bother our clients to change their code because they may have used animal.species = something hundreds of times throughout their code.

Fortunately, we have the property decorator. Read more about it here.

For this problem, you will utilize the property decorator to limit what species users can set their Animal object to. Please copy the following code into the file animal.py (please create the file and copy below code).

class Animal:

    # a class attribute of the valid species in our universe
    valid_species = {
        'cat',
        'dog',
        'duck',
        'elf',
        'goblin',
        'horse',
        'human',
        'mermaid',
        'nightingale',
        'pig',
        'swan',
        'wolf'
    }

    def __init__(self, name, species):
        self.name = name
        self._species = species

    def __repr__(self):
        return f'{self.name} ({self._species})'

Part A [15 points]:¶

We have also now designated the species attribute as "non-user-facing" by calling it _species because we do not want the user to access it directly. However, this presents a problem because in our first version of the Animal class, a client could access the species through the species attribute. You can check that the attributes of the Animal class are name and _species using the following steps (on Python shell):

>>> dog = Animal('Fido', 'dog')
>>> vars(dog)
{'name': 'Fido',  '_species' : 'dog'}

To prevent the client's previous code from breaking, modify the Animal class in animal.py by adding a species(self) method to the Animal class. The species method should return the _species attribute of this Animal. Apply the property decorator to this method.

If this is done correctly, then a client should still be able to retrieve the species of an Animal object as follows in the Python shell (you should use print() in an editor to print out):

>>> dog = Animal('Fido', 'dog')
>>> dog.species
'dog'

Part B [20 points]:¶

What happens when the client tries to set the value of the species attribute as in the following:

>>> dog.species = 'cat'

You don't need to write the answer to this question, but you should test it.

Thus to prevent the client's previous code from breaking, we need to create another method that:

1. Allows the client to set the species of an Animal object using .species
2. And checks that the species attribute is set to a species in our valid_species list.

Add another method species(self, into) to the Animal class. This method should set the _species attribute of this Animal to into, but before that, it makes sure that into is in the valid_species list. If into is not in the valid_species list, raise an Exception. Apply the species.setter decorator to this method.

If this is done correctly, then a client should still be able to set the species of an Animal object (within the restricted list) as follows, in a Python shell (in an editor, you should use print() to print out):

>>> dog = Animal('Fido', 'dog')
>>> dog.species
'dog'
>>> dog.species = 'cat'
>>> dog.species
'cat'
>>> dog.species = 'TheThing'
...
AssertionError: invalid species: TheThing

Do our clients need to change the implementation of their transform function now? Nope, and hopefully they give you a bonus!

Deliverables¶

• animal.py

Problem 2: Binary Search Tree¶

A binary search tree (BST) is a binary tree in which:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

The code below is a partially implemented binary search tree. BSTNode is a node in the binary search tree. It contains a key-value pair and has references to its child nodes. BSTTable is the binary search tree itself. It holds a reference to the root node of the tree and contains methods that manipulate the nodes. Each child of the root node and its child should be a BSTNode. A BSTTable can be used as a table to store key-value pairs. Our implementation will only be able to handle the case when the keys are comparable to each other. Simple client code of BSTTable looks like this:

greektoroman = BSTTable()
greektoroman.put('Athena',    'Minerva')
greektoroman.put('Eros',      'Cupid')
greektoroman.put('Aphrodite', 'Venus')
greektoroman.get('Eros')

and will return

'Cupid'

In this problem, we will implement the get and put method of BSTTable.

We start by copying the template code below into the file binary_search_tree.py.

Hint: You can print a BSTTable or BSTNode to see its structure. It's not pretty, but should be enough for debugging purposes. If you get lost, please try to draw the schematic on a paper step-by-step for each node creation and try to understand what your implemented functions do. For example,

print(greektoroman)

The above statement will print out:

BSTNode(Athena, Minerva)
|
|-(L)->BSTNode(Aphrodite, Venus)
|      |
|      |-(L)->None
|      |
|      |-(R)->None
|
|-(R)->BSTNode(Eros,Cupid)
|      |
|      |-(L)->None
|      |
|      |-(R)->None

Note: You may assume that the keys are unique.

class BSTNode:

    def __init__(self, key, val):
        self.key, self.val = key, val
        self.left = None
        self.right = None
        self.size = 1

    def __str__(self):
        return f'BSTNode({self.key}, {self.val})' + \
               '\n|\n|-(L)->' + '\n|      '.join(str(self.left ).split('\n')) + \
               '\n|\n|-(R)->' + '\n|      '.join(str(self.right).split('\n'))


class BSTTable:
    def __init__(self):
        self._root = None

    def __str__(self):
        return str(self._root)

    def __len__(self):
        return self._size(self._root)

    def put(self, key, val):
        self._root = self._put(self._root, key, val)

    def get(self, key):
        return self._get(self._root, key)

    def _put(self, node, key, val):
        pass # TODO

    def _get(self, node, key):
        pass # TODO

    @staticmethod
    def _size(node):
        return node.size if node else 0

Part A [30 points]:¶

The put method inserts a key-value pair into the BSTTable. It delegates the function call to _put. Please implement the non-public method _put. It takes a node, a key, and a val as arguments. node is the root of the subtree into which the key-value pair is to be inserted. After the insertion, the root of this subtree may change. _put should return the new root of this subtree. The difference of the input subtree and the returned subtree is that in the returned subtree, a new key-value pair has been inserted. If the key was already in the subtree, then we update the value of the corresponding node.

Note: We assume all the keys are of the same type and are comparable to each other with >, < and ==. So if all your keys are strings (e.g. greektoroman), they will be ordered lexicographically. If all your keys are numbers, they will be ordered from the smallest to the largest.

Hints:

• This is recursive.
• Think about the base case: what should be returned if the node passed in is None?
• Which subtree (left/right) should we insert if the node is not None?
• Remember to update the size of the nodes.
  • The size attribute of each BSTNode is the size of this subtree, i.e. the number of nodes including itself and all its descendants.

Part B [25 points]:¶

The get method returns the value with the corresponding key. It delegates the function call to _get. Please implement the non-public method _get. It takes a node and a key as an argument. It will search for a node with the same key under the subtree whose root is node. If there is such a node, return the val of this node. _get should raise a KeyError if no such node is found.

Deliverables¶

• binary_search_tree.py