Homework 4 | CS 61A Spring 2023
Homework 4: Trees, Data Abstraction
Due by 11:59pm on Thursday, March 2
Instructions
Download hw04.zip. Inside the archive, you will find a file called
hw04.py, along with a copy of the ok autograder.
Submission: When you are done, submit the assignment by uploading all code files you’ve edited to Gradescope. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on Gradescope. See Lab 0 for more instructions on
submitting assignments.
Using Ok: If you have any questions about using Ok, please
refer to this guide.
Readings: You might find the following references
Section 2.2
Section 2.3
Grading: Homework is graded based on
correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus.
This homework is out of 2 points.
Required questions
Getting Started Videos (enable JavaScript)
Getting Started Videos
These videos may provide some helpful direction for tackling the coding
problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
YouTube link
Q1: Mid-Semester Feedback
As part of this week’s homework, please fill out the
Mid-Semester Feedback form.
This survey is designed to help us make short term adjustments to the course
so that it works better for you. We appreciate your feedback. We may not be able
to make every change that you request, but we will read all the feedback and
consider it.
Confidentiality:
Your responses to the survey are confidential, and only the instructors
and head TAs will be able to see this data unanonymized.
More specifics on confidentiality can be found on the survey itself.
Once you finish the survey, you will be presented with a passphrase (if you miss
it, it should also be at the bottom of the confirmation email you receive). Put
this passphrase, as a string, on the line that says
passphrase = ‘*** PASSPHRASE HERE ***’ in the Python file for this assignment.
Use Ok to test your code:
python3 ok -q midsem_surveyCopy
Arms-length recursion
Tip: Adding extra code in a recursive function to handle examples that are already handled by existing base cases and recursive calls is redundant, adds complexity, and makes code harder to follow. One common example called arms-length recursion occurs when a base case is checked before a recursive call even though it would have been checked after the recursive call. Try to avoid this! For example, the lines marked # CAN BE REMOVED can (and should) be removed without changing the behavior of this function.
def min_depth(t):
“””Return the number of steps in the shortest path to a leaf in tree t.”””
if is_leaf(t):
for b in branches(t): # CAN BE REMOVED
if is_leaf(b): # CAN BE REMOVED
return 1 # CAN BE REMOVED
return 1 + min([min_depth(b) for b in branches(t)])
Acknowledgements
This mobile example is based on
a classic problem from MIT Structure and Interpretation of Computer Programs,
Section 2.2.2.
We are making a planetarium mobile. A mobile is a type of hanging sculpture. A binary mobile consists of two
arms. Each arm is a rod of a certain length, from which hangs either a planet
or another mobile. For example, the below diagram shows the left and right arms of Mobile A,
and what hangs at the ends of each of those arms.
We will represent a binary mobile using the data abstractions below.
A mobile must have both a left arm and a right arm.
An arm has a positive length and must have something hanging at the end, either a mobile or planet.
A planet has a positive mass, and nothing hanging from it.
Below are the implementations of the various data abstractions used in mobiles.
The mobile and arm data abstractions have been completed for you.
Implementation of the Mobile Data Abstraction (for your reference, no need to do anything here):
def mobile(left, right):
“””Construct a mobile from a left arm and a right arm.”””
assert is_arm(left), “left must be a arm”
assert is_arm(right), “right must be a arm”
return [‘mobile’, left, right]
def is_mobile(m):
“””Return whether m is a mobile.”””
return type(m) == list and len(m) == 3 and m[0] == ‘mobile’
def left(m):
“””Select the left arm of a mobile.”””
assert is_mobile(m), “must call left on a mobile”
return m[1]
def right(m):
“””Select the right arm of a mobile.”””
assert is_mobile(m), “must call right on a mobile”
return m[2]
Implementation of the Arm Data Abstraction (for your reference, no need to do anything here):
def arm(length, mobile_or_planet):
“””Construct a arm: a length of rod with a mobile or planet at the end.”””
assert is_mobile(mobile_or_planet) or is_planet(mobile_or_planet)
return [‘arm’, length, mobile_or_planet]
def is_arm(s):
“””Return whether s is a arm.”””
return type(s) == list and len(s) == 3 and s[0] == ‘arm’
def length(s):
“””Select the length of a arm.”””
assert is_arm(s), “must call length on a arm”
return s[1]
def end(s):
“””Select the mobile or planet hanging at the end of a arm.”””
assert is_arm(s), “must call end on a arm”
return s[2]
Q2: Weights
Implement the planet data abstraction by completing the planet constructor
and the mass selector so that a planet is represented using a two-element list
where the first element is the string ‘planet’ and the second element is its mass.
def planet(mass):
“””Construct a planet of some mass.”””
assert mass > 0
“*** YOUR CODE HERE ***”
def mass(w):
“””Select the mass of a planet.”””
assert is_planet(w), ‘must call mass on a planet’
“*** YOUR CODE HERE ***”
def is_planet(w):
“””Whether w is a planet.”””
return type(w) == list and len(w) == 2 and w[0] == ‘planet’
The total_weight function demonstrates the use of the mobile, arm,
and planet abstractions. You do NOT need to implement anything here. You may use
the total_weight function in questions 3 and 4.
def examples():
t = mobile(arm(1, planet(2)),
arm(2, planet(1)))
u = mobile(arm(5, planet(1)),
arm(1, mobile(arm(2, planet(3)),
arm(3, planet(2)))))
v = mobile(arm(4, t), arm(2, u))
return t, u, v
def total_weight(m):
“””Return the total weight of m, a planet or mobile.
>>> t, u, v = examples()
>>> total_weight(t)
>>> total_weight(u)
>>> total_weight(v)
if is_planet(m):
return mass(m)
assert is_mobile(m), “must get total weight of a mobile or a planet”
return total_weight(end(left(m))) + total_weight(end(right(m)))
Run the ok tests for total_weight to make sure that your planet and mass
functions are implemented correctly.
Use Ok to test your code:
python3 ok -q total_weightCopy
Q3: Balanced
Implement the balanced function, which returns whether m is a balanced
mobile. A mobile is balanced if both of the following conditions are met:
The torque applied by its left arm is equal to the torque applied by its right
arm. The torque of the left arm is the length of the left rod multiplied by the
total weight hanging from that rod. Likewise for the right. For example,
if the left arm has a length of 5, and there is a mobile hanging at the end
of the left arm of total weight 10, the torque on the left side of our mobile is 50.
Each of the mobiles hanging at the end of its arms is itself balanced.
Planets themselves are balanced, as there is nothing hanging off of them.
Reminder: You may use the total_weight function defined for you in Question 2 (as well as any of the
other functions defined in Question 2).
def balanced(m):
“””Return whether m is balanced.
>>> t, u, v = examples()
>>> balanced(t)
>>> balanced(v)
>>> w = mobile(arm(3, t), arm(2, u))
>>> balanced(w)
>>> balanced(mobile(arm(1, v), arm(1, w)))
>>> balanced(mobile(arm(1, w), arm(1, v)))
>>> from construct_check import check
>>> # checking for abstraction barrier violations by banning indexing
>>> check(HW_SOURCE_FILE, ‘balanced’, [‘Index’])
“*** YOUR CODE HERE ***”
Use Ok to test your code:
python3 ok -q balancedCopy
Q4: Totals
Implement totals_tree, which takes in a mobile or planet and returns a
tree whose root label is the total weight of the input. For a planet, totals_tree
should return a leaf. For a mobile, totals_tree should return a tree whose
label is that mobile’s total weight, and whose branches are totals_trees for the
ends of its arms. As a reminder, the description of the tree data abstraction can be
found here.
def totals_tree(m):
“””Return a tree representing the mobile with its total weight at the root.
>>> t, u, v = examples()
>>> print_tree(totals_tree(t))
>>> print_tree(totals_tree(u))
>>> print_tree(totals_tree(v))
>>> from construct_check import check
>>> # checking for abstraction barrier violations by banning indexing
>>> check(HW_SOURCE_FILE, ‘totals_tree’, [‘Index’])
“*** YOUR CODE HERE ***”
Use Ok to test your code:
python3 ok -q totals_treeCopy
More Trees
Q5: Replace Loki at Leaf
Define replace_loki_at_leaf, which takes a tree t and a value lokis_replacement. replace_loki_at_leaf returns a new tree that’s the same as t except
that every leaf label equal to “loki” has been replaced with lokis_replacement.
If you want to learn about the Norse mythology referenced in this problem, you can read about it here.
def replace_loki_at_leaf(t, lokis_replacement):
“””Returns a new tree where every leaf value equal to “loki” has
been replaced with lokis_replacement.
>>> yggdrasil = tree(‘odin’,
… [tree(‘balder’,
… [tree(‘loki’),
… tree(‘freya’)]),
… tree(‘frigg’,
… [tree(‘loki’)]),
… tree(‘loki’,
… [tree(‘sif’),
… tree(‘loki’)]),
… tree(‘loki’)])
>>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
>>> print_tree(replace_loki_at_leaf(yggdrasil, ‘freya’))
>>> laerad == yggdrasil # Make sure original tree is unmodified
“*** YOUR CODE HERE ***”
Use Ok to test your code:
python3 ok -q replace_loki_at_leafCopy
Q6: Has Path
Write a function has_path that takes in a tree t and a string word. It
returns True if there is a path that starts from the root where the entries
along the path spell out the word, and False otherwise. (This data structure
is called a trie, and it has a lot of cool applications, such as autocomplete).
You may assume that every node’s label is exactly one character.
def has_path(t, word):
“””Return whether there is a path in a tree where the entries along the path
spell out a particular word.
>>> greetings = tree(‘h’, [tree(‘i’),
… tree(‘e’, [tree(‘l’, [tree(‘l’, [tree(‘o’)])]),
… tree(‘y’)])])
>>> print_tree(greetings)
>>> has_path(greetings, ‘h’)
>>> has_path(greetings, ‘i’)
>>> has_path(greetings, ‘hi’)
>>> has_path(greetings, ‘hello’)
>>> has_path(greetings, ‘hey’)
>>> has_path(greetings, ‘bye’)
>>> has_path(greetings, ‘hint’)
assert len(word) > 0, ‘no path for empty word.’
“*** YOUR CODE HERE ***”
Use Ok to test your code:
python3 ok -q has_pathCopy
Optional Questions
Data Abstraction
Feel free to reference
Section 2.2
for more information on data abstraction.
Acknowledgements. This interval arithmetic example is based on
a classic problem from Structure and Interpretation of Computer Programs,
Section 2.1.4.
Introduction. Alyssa P. Hacker is designing a system to help people
solve engineering problems. One feature she wants to provide in her
system is the ability to manipulate inexact quantities (such as
measurements from physical devices) with known precision, so that
when computations are done with such approximate quantities the results
will be numbers of known precision. For example, if a measured quantity
x lies between two numbers a and b, Alyssa would like her system to
use this range in computations involving x.
Alyssa’s idea is to implement interval arithmetic as a set of
arithmetic operations for combining “intervals” (objects that represent
the range of possible values of an inexact quantity). The result of
adding, subracting, multiplying, or dividing two intervals is also an
interval, one that represents the range of the result.
Alyssa suggests the existence of an abstraction called an
“interval” that has two endpoints: a lower bound and an upper bound.
She also presumes that, given the endpoints of an interval, she can
create the interval using data abstraction. Using this constructor and the appropriate selectors,
she defines the following operations:
def str_interval(x):
“””Return a string representation of interval x.”””
return ‘{0} to {1}’.format(lower_bound(x), upper_bound(x))
def add_interval(x, y):
“””Return an interval that contains the sum of any value in interval x and
any value in interval y.”””
lower = lower_bound(x) + lower_bound(y)
upper = upper_bound(x) + upper_bound(y)
return interval(lower, upper)
Q7: Interval Abstraction
Alyssa’s program is incomplete because she has not specified the implementation
of the interval abstraction. She has implemented the constructor for you; fill
in the implementation of the selectors.
def interval(a, b):
“””Construct an interval from a to b.”””
assert a <= b, 'Lower bound cannot be greater than upper bound'
return [a, b]
def lower_bound(x):
"""Return the lower bound of interval x."""
"*** YOUR CODE HERE ***"
def upper_bound(x):
"""Return the upper bound of interval x."""
"*** YOUR CODE HERE ***"
Use Ok to unlock and test your code:
python3 ok -q interval -u
python3 ok -q intervalCopy
Q8: Interval Arithmetic
After implementing the abstraction, Alyssa decided to implement a few interval arithmetic functions.
This is her current implementation for interval multiplication.
Unfortunately there are some data abstraction violations,
so your task is to fix this code
before someone sets it on fire.
def mul_interval(x, y):
"""Return the interval that contains the product of any value in x and any
value in y."""
p1 = x[0] * y[0]
p2 = x[0] * y[1]
p3 = x[1] * y[0]
p4 = x[1] * y[1]
return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]
Use Ok to unlock and test your code:
python3 ok -q mul_interval -u
python3 ok -q mul_intervalCopy
Interval Subtraction
Using a similar approach as mul_interval and add_interval, define a subtraction function for
intervals. If you find yourself repeating code, see if you can reuse functions that have already been implemented.
def sub_interval(x, y):
"""Return the interval that contains the difference between any value in x
and any value in y."""
"*** YOUR CODE HERE ***"
Use Ok to unlock and test your code:
python3 ok -q sub_interval -u
python3 ok -q sub_intervalCopy
Interval Division
Alyssa implements division below by multiplying by the reciprocal of
y. A systems programmer looks over Alyssa's
shoulder and comments that it is not clear what it means to divide by
an interval that spans zero. Add an assert statement to Alyssa's code
to ensure that no such interval is used as a divisor:
def div_interval(x, y):
"""Return the interval that contains the quotient of any value in x divided by
any value in y. Division is implemented as the multiplication of x by the
reciprocal of y."""
"*** YOUR CODE HERE ***"
reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y))
return mul_interval(x, reciprocal_y)
Use Ok to unlock and test your code:
python3 ok -q div_interval -u
python3 ok -q div_intervalCopy
Q9: Par Diff
After considerable work, Alyssa P. Hacker delivers her finished system. Several
years later, after she has forgotten all about it, she gets a frenzied call from
an irate user, Lem E. Tweakit. It seems that Lem has noticed that the
formula for parallel resistors
can be written in two algebraically equivalent ways:
par1(r1, r2) = (r1 * r2) / (r1 + r2)
par2(r1, r2) = 1 / (1/r1 + 1/r2)
He has written the following two programs, each of which computes the
parallel_resistors formula differently:
def par1(r1, r2):
return div_interval(mul_interval(r1, r2), add_interval(r1, r2))
def par2(r1, r2):
one = interval(1, 1)
rep_r1 = div_interval(one, r1)
rep_r2 = div_interval(one, r2)
return div_interval(one, add_interval(rep_r1, rep_r2))
Lem points out that Alyssa's program gives different answers for the two ways of computing. Find two intervals r1 and r2 that demonstrate the difference in behavior between par1 and par2 when passed into each of the two functions.
Demonstrate that Lem is right. Investigate the behavior of the system
on a variety of arithmetic expressions. Make some intervals r1 and
r2, and show that par1 and par2 can give different results.
def check_par():
"""Return two intervals that give different results for parallel resistors.
>>> r1, r2 = check_par()
>>> x = par1(r1, r2)
>>> y = par2(r1, r2)
>>> lower_bound(x) != lower_bound(y) or upper_bound(x) != upper_bound(y)
r1 = interval(1, 1) # Replace this line!
r2 = interval(1, 1) # Replace this line!
return r1, r2
Use Ok to test your code:
python3 ok -q check_parCopy
Exam Practice
Homework assignments will also contain prior exam questions for you to try.
These questions have no submission component; feel free to attempt them if you’d like some practice!
Summer 2021 MT Q4: Maximum Exponen-tree-ation
Summer 2019 MT Q8: Leaf It To Me
Summer 2017 MT Q9: Temmie Flakes
Required questions
Getting Started Videos
Q1: Mid-Semester Feedback
Arms-length recursion
Q2: Weights
Q3: Balanced
Q4: Totals
More Trees
Q5: Replace Loki at Leaf
Q6: Has Path
Optional Questions
Data Abstraction
Q7: Interval Abstraction
Q8: Interval Arithmetic
Q9: Par Diff
Exam Practice
Weekly Schedule
Office Hours
Studying Guide
Debugging Guide
Composition Guide
Pair Programming
Assignments