393 views
owned this note
# ARCHIVED: ~~Lab 8: Tables, Lists, Datatypes, and Trees -- Oh My!~~
:::danger
## This is the S26 version of this document. Refer to the [course webpage](https://brown-csci0111.github.io/pages/home.html) for the up-to-date version.
:::
This lab is an important junction for two reasons: it's where those aiming for 200 should start ramping up to harder problems, and it's our last Pyret lab before we start Python. As a result, this lab is structured with some options for you to choose from.
Everyone will do the first set of problems. Further down, you'll see two options:
- Option 1 (writing functions over lists of datatypes). If you are still getting the hang of writing functions over lists, work on these problems (we will continue to write programs over lists in Python, so this is useful practice).
- Option 2 (programming over trees). If you are headed to 200, work on Option 2. Those not heading to 200 but who feel comfortable with writing list functions are also welcome to work on option 2.
## Learning Objectives
* Explain differences between data structures
* Choose the correct data structures based on program goals and specifications
:::info
## The first part of the lab is done interactively on mentimeter! Your TAs will explain what to do.
:::
After you come back from this part, work on:
## Matching Ads, One Last Time
The trees for the guessing game are examples of what are called *decision trees*: a series of questions about characteristics of an object or situation are asked, working down the tree until a decision (or guess) is reached at the bottom of the tree.
Some real-world ad-matching systems are based on decision trees. When a user is logged into a site, a program asks the site (e.g. Google) the questions in the tree about the user (e.g., "what gender are they", "what age-range are they", "where do they live", etc): the bottom of the tree contains the ads to show with users with traits from the answers.
In theory, we have shown you enough programming at this point to write an ad-matcher based on decision trees. In practice, that program would be a bit harder than what you're prepared for. Those who come to CS200, however, will do a course project that constructs a decision-tree from a table of data about ad-like information.
### Option 1: Practice with Lists in Datatypes
Consider the following datatype, which represents information about a single course:
```
data Course:
| lecture(name :: String, roster :: List<String>)
end
```
For now, we're just considering lecture-based courses, where each course contains the list of names of students who are taking the course.
**Task 1:** Copy this datatype into your file and make a couple of example courses.
**Task 2:** Write a function that takes a `Course` and a student name and returns a course. The returned course should have the student name added to the roster.
**Task 3:** Some years, it feels like certain students' first names appear many times. Write a function `count-name` which takes a `Course` and a name and returns the number of students with that first name who are in the course roster. Assume every name in the roster is formatted like this 'FIRSTNAME LASTNAME'.
Do this with explicit recursion, rather than built-ins.
*Hint:* The question here is how to write a recursive function to process a list that is inside of a datatype. You should use two functions here: a recursive one on a list of strings, and a non-recursive one on the datatype that calls your recursive one.
**Task 4:** We want to represent more information about our students than just their names!
* Create a new `Student` datatype that holds the student's name and semester level.
* Create a new `CourseStudent` datatype. This should look very similar to the `Course` datatype, but it should use your `Student` datatype.
**Task 5:** Where in your `count-name` function would you need to make edits in order to accommodate this change in datatype? You don't need to write the code (unless you want the practice). The point is to think about what parts of your original code would change or stay the same with this extended definition.
### Option 2: Working with Trees (200-bound/Challenge)
You will write several tree programs as part of the bridge work for CS200. For this lab, we want to make sure that you understand how recursion works on trees before you start writing programs to process them.
Consider the following program, which returns the name of one person with the given eye color from the given tree. Your goal is to understand which name gets returned and why.
**Task 1:** Look at the program and the `where` cases. *Without running the code*, predict what the code will produce on each case.
```=python
data AncTree:
| noInfo
| person(name :: String, born :: Number, eye :: String, parent-1 :: AncTree, parent-2 :: AncTree)
end
robert-tree = person("Robert", 1893, "brown", noInfo, noInfo)
laura-tree = person("Laura", 1920, "blue", noInfo, noInfo)
john-tree = person("John", 1920, "green", noInfo, robert-tree)
ellen-tree = person("Ellen", 1945, "brown", laura-tree, john-tree)
bill-tree = person("Bill", 1946, "green", noInfo, noInfo)
susan-tree = person("Susan", 1971, "blue", ellen-tree, bill-tree)
charlie-tree = person("Charlie", 1972, "green", noInfo, noInfo)
anna-tree = person("Anna", 1997, "blue", susan-tree, charlie-tree)
NOBODY-FOUND = "Nobody was found!"
fun find-eye(at :: AncTree, with-color :: String) -> String:
doc: "return name of one person with given eye color (assume there is one)"
cases (AncTree) at:
| noInfo => NOBODY-FOUND
| person(n, b, e, p1, p2) =>
if (e == with-color): n
else:
find-eye-p1 = find-eye(p1, with-color)
if not(find-eye-p1 == NOBODY-FOUND): find-eye-p1
else: find-eye(p2, with-color)
end
end
end
where:
find-eye(anna-tree, "green") is ...
find-eye(anna-tree, "brown") is ...
end
```
**Task 2:** In lecture, we showed using an execution diagram to track the evolution of recursive function calls. Draw an execution diagram for the program execution from the first `where` example, until the point when the `if`-expression evaluates to true. Indicate the order in which the functions cals get *called* and in which order they *finish running and return a value.* (If you color-code your diagram, this is easier to list off).
Refer back to **Drill 21** to see how to format execution diagrams for trees.
Use this image as a starting point:
**Task 3:** What is the sequence of values for `p1` across the calls to `find-eye`, assuming we search for a name that is not in the tree? Assume we start with the call `find-eye(anna-tree, "X")`. Make a list of the calls to `find-eye` that occur in order, in a form like:
- `find-eye(anna-tree, "X")`
- `find-eye(susan-tree, "X")`
- ...
Then annotate each call with the value that `p1` will have in the directory at the time that the call gets made. What do you notice about that sequence after you've finished it?
**Task 4:** Write a program `all-blue-eyed` that takes an `AncTree` and returns a list of the names of all people with blue eyes.
**Task 5:** Make a copy of `all-blue-eyed` and modify it to take a predicate (a function that returns a boolean) that decides which people to include in the output list (like a form of filter on trees). Try this function on a couple of examples.
___
### *CHECKPOINT:* Call over a TA once you reach this point.
---
> Brown University CSCI 0111 (Spring 2026)
> Have questions? Refer to [Ed](https://edstem.org/us/courses/93677)
> Check out our glorious [Spotify](https://open.spotify.com/playlist/0UdtGEq1aamMp78T0Ehxg4) playlist!
<iframe data-testid="embed-iframe" style="border-radius:12px" src="https://open.spotify.com/embed/playlist/0UdtGEq1aamMp78T0Ehxg4?utm_source=generator" width="100%" height="352" frameBorder="0" allowfullscreen="" allow="autoplay; clipboard-write; encrypted-media; fullscreen; picture-in-picture" loading="lazy"></iframe>
> **Feedback form** <iframe src="https://docs.google.com/forms/d/e/1FAIpQLSdjTJkyCYkLXcnYfzkugwD8FDuJQZwM5SAER4pwvU_QxTuRSw/viewform?embedded=true" width="640" height="977" frameborder="0" marginheight="0" marginwidth="0">Loading…</iframe>