Lab 5: Data Abstraction, Trees
Due by 11:59pm on Tuesday, July 11.
Starter Files
Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Trees
A tree
is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your cs61a
folder, you have folders separating your projects
, lab
assignments, and homework
. The next level is folders that separate different assignments, hw01
, lab01
, hog
, etc., and inside those are the files themselves, including the starter files and ok
. Below is an incomplete diagram of what your cs61a
directory might look like.
As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.
Data Abstraction
Data abstraction is a powerful concept in computer science that allows programmers to treat code as objects. For example, using code to represent cars, chairs, people, and so on. That way, programmers don't have to worry about how code is implemented; they just have to know what it does.
Data abstraction mimics how we think about the world. If you want to drive a car, you don't need to know how the engine was built or what kind of material the tires are made of to do so. You just have to know how to use the car for driving itself, such as how to turn the wheel or press the gas pedal.
A data abstraction consists of two types of functions:
- Constructors: functions that build the abstract data type.
- Selectors: functions that retrieve information from the data type.
Programmers design data abstractions to abstract away how information is stored and calculated such that the end user does not need to know how constructors and selectors are implemented. The nature of abstraction allows whoever uses them to assume that the functions have been written correctly and work as described.
Required Questions
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.
Trees
Q1: Finding Berries!
The squirrels on campus need your help! There are a lot of trees on campus and
the squirrels would like to know which ones contain berries. Define the function
berry_finder
, which takes in a tree and returns True
if the tree contains a
node with the value 'berry'
and False
otherwise.
Hint: To iterate through each of the branches of a particular tree, you can consider using a
for
loop to get each branch.
def berry_finder(t):
"""Returns True if t contains a node with the value 'berry' and
False otherwise.
>>> scrat = tree('berry')
>>> berry_finder(scrat)
True
>>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
>>> berry_finder(sproul)
True
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> berry_finder(numbers)
False
>>> t = tree(1, [tree('berry',[tree('not berry')])])
>>> berry_finder(t)
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q berry_finder
Q2: 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'))
odin
balder
freya
freya
frigg
freya
loki
sif
freya
freya
>>> laerad == yggdrasil # Make sure original tree is unmodified
True
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q replace_loki_at_leaf
Data Abstraction
Say we have an abstract data type for cities. A city has a name, a latitude coordinate, and a longitude coordinate.
Our data abstraction has one constructor:
make_city(name, lat, lon)
: Creates a city object with the given name, latitude, and longitude.
We also have the following selectors in order to get the information for each city:
get_name(city)
: Returns the city's nameget_lat(city)
: Returns the city's latitudeget_lon(city)
: Returns the city's longitude
Here is how we would use the constructor and selectors to create cities and extract their information:
>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> new_york = make_city('New York City', 74, 40)
>>> get_lon(new_york)
40
All of the selector and constructor functions can be found in the lab file, if you are curious to see how they are implemented. However, the point of data abstraction is that we do not need to know how an abstract data type is implemented, but rather just how we can interact with and use the data type.
Q3: Distance
We will now implement the function distance
, which computes the
distance between two city objects. Recall that the distance between two
coordinate pairs (x1, y1)
and (x2, y2)
can be found by calculating
the sqrt
of (x1 - x2)**2 + (y1 - y2)**2
. We have already imported
sqrt
for your convenience. Use the latitude and longitude of a city as
its coordinates; you'll need to use the selectors to access this info!
from math import sqrt
def distance(city_a, city_b):
"""
>>> city_a = make_city('city_a', 0, 1)
>>> city_b = make_city('city_b', 0, 2)
>>> distance(city_a, city_b)
1.0
>>> city_c = make_city('city_c', 6.5, 12)
>>> city_d = make_city('city_d', 2.5, 15)
>>> distance(city_c, city_d)
5.0
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q distance
Q4: Closer city
Next, implement closer_city
, a function that takes a latitude,
longitude, and two cities, and returns the name of the city that is
relatively closer to the provided latitude and longitude.
You may only use the selectors and constructors introduced above and the
distance
function you just defined for this question.
Hint: How can you use your
distance
function to find the distance between the given location and each of the given cities?
def closer_city(lat, lon, city_a, city_b):
"""
Returns the name of either city_a or city_b, whichever is closest to
coordinate (lat, lon). If the two cities are the same distance away
from the coordinate, consider city_b to be the closer city.
>>> berkeley = make_city('Berkeley', 37.87, 112.26)
>>> stanford = make_city('Stanford', 34.05, 118.25)
>>> closer_city(38.33, 121.44, berkeley, stanford)
'Stanford'
>>> bucharest = make_city('Bucharest', 44.43, 26.10)
>>> vienna = make_city('Vienna', 48.20, 16.37)
>>> closer_city(41.29, 174.78, bucharest, vienna)
'Bucharest'
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q closer_city
Q5: Don't violate the abstraction barrier!
Note: this question has no code-writing component (if you implemented the previous two questions correctly).
When writing functions that use an data abstraction, we should use the constructor(s) and selector(s) whenever possible instead of assuming the data abstraction's implementation. Relying on a data abstraction's underlying implementation is known as violating the abstraction barrier, and we never want to do this!
It's possible that you passed the doctests for the previous questions even if you violated the abstraction barrier. To check whether or not you did so, run the following command:
Use Ok to test your code:
python3 ok -q check_city_abstraction
The check_city_abstraction
function exists only for the doctest, which swaps
out the implementations of the original abstraction with something else, runs
the tests from the previous two parts, then restores the original abstraction.
The nature of the abstraction barrier guarantees that changing the implementation of an data abstraction shouldn't affect the functionality of any programs that use that data abstraction, as long as the constructors and selectors were used properly.
If you passed the Ok tests for the previous questions but not this one, the fix is simple! Just replace any code that violates the abstraction barrier with the appropriate constructor or selector.
Make sure that your functions pass the tests with both the first and the second implementations of the data abstraction and that you understand why they should work for both before moving on.
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Optional Questions
These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!
Trees
Q6: Recursion on Trees
Define a function dejavu
, which takes in a tree of numbers t
and a number n
. It returns True
if there is a path from the root to a leaf such that the sum of the numbers along that path is n
and False
otherwise.
def dejavu(t, n):
"""
>>> my_tree = tree(2, [tree(3, [tree(5), tree(7)]), tree(4)])
>>> dejavu(my_tree, 12) # 2 -> 3 -> 7
True
>>> dejavu(my_tree, 5) # Sums of partial paths like 2 -> 3 don ’t count
False
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q dejavu
Q7: Hailstone Tree
We can represent the hailstone sequence as a tree in the figure below,
showing the route different numbers take to reach 1. Remember that a hailstone
sequence starts with a number n
, continuing to n/2
if n
is even or 3n+1
if n
is odd, ending with 1. Write a function hailstone_tree(n, h)
which generates a tree of height h
, containing hailstone numbers that
will reach n
.
Hint: A node of a hailstone tree will always have at least one, and at most two branches (which are also hailstone trees). Under what conditions do you add the second branch?
def hailstone_tree(n, h):
"""Generates a tree of hailstone numbers that will reach N, with height H.
>>> print_tree(hailstone_tree(1, 0))
1
>>> print_tree(hailstone_tree(1, 4))
1
2
4
8
16
>>> print_tree(hailstone_tree(8, 3))
8
16
32
64
5
10
"""
if _________________________________:
return _________________________________
branches = _________________________________
if ___________ and ___________ and ___________:
branches += _________________________________
return tree(n, branches)
Use Ok to test your code:
python3 ok -q hailstone_tree