Homework 3: Trees and Objects
The goals of this assignment are:
- To get practice implementing methods on classes
- To get practice designing and developing programs on trees
- HW3 is due on Thursday, October 15th at 9pm EST.
Setup and Handin
In order to setup hw3, make a new PyCharm Project and name it hw3. For testing, make sure you install pytest in the new PyCharm Project. The functions you need to complete will be outlined later, but for now make sure you create the four following files:
tree.py you will be working with HTMLTrees, so you will need to create
an additional file named
htmltree.py and add this code to it. This
contains the structure of the HTMLTree, which is imported into
You may submit as many times as you want. Only your latest submission will be graded. This means that if you submit after the deadline, you will be using a late day – so do NOT submit after the deadline unless you plan on using late days.
Because all we need are the files, you do not need to submit the whole project folder. As long as the file you create has the same name as what needs to be submitted, you’re good to go!
If you are using late days, make sure to make a note of that in your README. Remember, you may only use a maximum of 3 late days per assignment. If the assignment is late (and you do NOT have anymore late days) no credit will be given.
Please don’t put your name anywhere in any of the handin files–we grade assigments anonymously!
You can follow this step-by-step guide for submitting assignments through Gradescope here.
Your friendly TAs and Professor are here to help with this assignment! You can find our schedule for office hours here.
Part 1: For the love of Newton
On our amazing race for cs112 we make a stop by Woolsthorpe Manor, the famous location where Isaac Newton reportedly came up with the law of gravity. While touring the estate, the guide informs us that our next clue is at the top of the tree! We want to reach the top but we don’t know how high our ladder needs to be. Doug points out that we can model the famous tree with an html tree. We need your help so we can understand more about the tree and get to our next clue!
We’d like you to write the following functions on
HTMLTrees in the
tree_height computes the maximum distance from the root to any leaf. This
function should take an
HTMLTree and return an integer. The height of a tree
with no children is 1; the height of a tree with children is the maximum height
of any of its children plus 1.
has_strong_grandchildren should return
True if any of the grandchildren of
the node at the root of the tree (i.e., children of its children) have the
"strong" tag. Note that it doesn’t matter whether the root of the tree or any
of its children are
strong, we only care about the grandchildren.
has_strong_grandchildren should take an
HTMLTree and return a boolean.
Part 2: Getting the message
Now that we have our tree, it’s time to spread our message with everyone in the class. Just as we begin to text every one the clue, our messaging app loses international coverage! How are we ever going to tell everyone about our next leg of the journey? It’s up to you to build a messaging class that we can use to share this info and keep our race going.
You should write code for this part in
messagecenter.py. Here’s some starter code:
class Message: def __init__(self, from_user: str, to_user: str, contents: str): self.from_user = from_user self.to_user = to self.contents = contents self.read = False def mark_read(self): self.read = True
For this part, you’ll write some code to implement a messaging
application–think WhatsApp. Your application will track messages (as a list of
Message objects, defined above) and groups, which are sets of users. Users can
send messages either to other users or to a group; sending a message to a group
results in it being sent to every user in the group. Your messaging applicaiton
will be implemented as a class called
MessageCenter class should implement the methods below. Remember that
all of your methods need to take
self as their first argument! We list the
other arguments below.
The __init__ method doesn’t need to take any arguments besides
groups fields to the object; these should be an
empty list responsible for keeping track of the messages and an empty hashtable
in charge of the different groups present in the message center, respectively.
This method should take (in addition to
self) the name of a group (a string)
and the name of a user (also a string). It should add a group with the given
name if it doesn’t exist, and then add the named user to the group if it’s not
already in the group.
add_direct_message should take (in addition to
self) two users and a
message body. It should create a message with the given users and body and store
it in the
add_group_message should take (in addition to
self) a user, a group, and a
message body. If the given group exists, it should add messages with the given
body from the given user to every member of the group.
next_message should take (in addition to
self) a user and return the first
unread message in the messages list addressed to that user. Before returning
the message, it should mark the message as read using the
message_history should take (in addition to
self) two users and return all
of the messages (read or unread) between those two users–messages from the
first user to the second user and vice versa.