CS61A Homework 6

Due by 11:59 PM on (that is, the end of) Tuesday, 7/10

This homework must be submitted online. We do not require a paper copy. If you would like a reader to give you written feedback on your homework, submit a paper copy to the homework box.

To turn in the electronic copy, submit all of your answers in a file named hw6.py. Follow the instructions here to submit the electronic copy.

Readings. All problems in this homework can be solved with the subset of Python 3 introduced in sections 1-2.4 of the lecture notes.

If you would like, you can use the template file hw6.py. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw06/hw6.py .

to copy it into your current directory.

In this homework we will be using the itree abstract data type. The file itree.py defines this ADTs along with some useful utility functions for manipulating them. On the lab computers, you should be able to import from these modules without any additional setup. READ THIS FILE! It contains functions we might not have introduced in lecture that might or might not be useful for solving these questions.

Q1. Define a function depth that, given an ITree, t, and a value, v, finds the depth at which v appears as a datum in the tree. Depth here refers to distance from the root, t. The node t itself is at depth 0; its children are at depth 1, etc. Assume that v appears at most once in the tree. Return None if it does not appear.

Q2. Define a function prune_leaves that, given an ITree, t, and a tuple of values, vals, and produces a tree with all leaves that contain one of the items in vals removed. Do not attempt to try to remove non-leaf nodes and do not remove leaves that do not match any of the items in vals. If you have to remove the root of a tree, return None.

Q3. Define a function sprout_leaves that, given an ITree, t, and a tuple of values, vals, and produces a tree with every leaf having new children that contain each of the items in vals. Do not add new children to non-leaf nodes.

Q4. Define a function same_shape that, given two ITrees, t1 and t2, returns True if the two trees have the same shape (but not necessarily the same data in each node) and False otherwise.

Q5. A mobile is a type of hanging sculpture. For example, here is a picture of a mobile created by Alexander Calder.

A simple binary mobile consists of two branches, left and right. Each branch is a rod of a certain length, from which hangs either a weight or another mobile. Such a mobile is balanced (meaning that it will not fall over to one side and will hang horizontally) if every "sub-mobile" (the mobiles that hang to the left or the right) is balanced and the product of the length of the left branch times the total weight on the left branch is equal to the product of the length of the right branch times the total weight on the right branch.

In the template file hw6.py we have implemented abstract data types for representing mobiles and branches. Using these abstract data types, implement the functions total_weight, which finds the total weight of a mobile, and is_balanced, which takes a mobile m and returns True if the mobile is properly balanced.