752 views
owned this note
<style>
h3 {
border-bottom: 1px solid #ccc;
}
section {
margin-bottom: 2rem;
padding: 0em 1em;
padding-bottom: 1em;
border-radius: 4px;
background-color: #f7f7f7;
border: 1px solid #ccc;
}
summary {
font-weight: bolder;
}
summary:hover {
text-decoration: underline;
}
.todo {
color: #ff00ff;
border: 2px dashed #ff00ff;
padding: 0em 1em;
border-radius: 5px;
//display: none; // UNCOMMENT TO HIDE TODOs
}
</style>
# Homework 1C-from-OO (Spring 2026)
**Due: Friday, February 6th at 11:59 p.m.**
:::info
**Collaboration Policy:** *You may collaborate as much as you want on this assignment* (this is more flexible than the normal course policy). The goal is to get everyone up to speed on Java. You are required to turn this in, but it will be weighted lightly in final grades. That said, we strongly encourage you to actively try writing these on your own while collaborating, as future assignments will assume you can handle these sorts of problems independently.
:::
**Need help?** Find us, as well as questions and answers from other students, on EdStem, or come to hours.
[**Handin Instructions**](#How-to-Hand-In) are at the end of the document.
## Learning Objectives
In this assignment, you will:
- Practice working with tree-like data structures
- Practice converting lists into tree-like data structures
- Practice runtime annotation
- Practice reasoning about design with tree-like datatypes
:::info
**Note on "runtime annotation":** For this homework, we are not asking for line-by-line `+1` style counting. Instead, you will write short comments about runtime using big-O notation in Task 3-C, and you should clearly state what `N` represents in your analysis.
:::
## Stencil Code and Assignment Setup
Using this **[GitHub Classroom link](https://classroom.github.com/a/ZmgZIE-S)**, accept the assignment and create a repository for your code. **Be sure to follow the [Java Stencil setup guide](https://docs.cs200.io/s/java-stencil-setup-guide)** for instructions on how to do this.
This assignment requires that you have IntelliJ installed and set up for this course. For details on the setup process, please see the [IntelliJ Setup Guide](https://docs.cs200.io/s/intellij-guide). If you're having trouble, the guide includes a [Common Bugs/FAQ](https://docs.cs200.io/s/intellij-guide#Common-BugsFAQ) section which might help.
Please make sure to read our [Gradescope submission guide](https://docs.cs200.io/gradescope-submission-guide) before handing in your assignment!
:::danger
:warning: **Important warning for CS15 students**: CS200 uses IntelliJ a little differently than you may be accustomed to in CS15.
In CS200, **you need to re-open IntelliJ on the folder for each assignment you work on** (i.e., the folder you cloned from git, such that appears as the top-level folder in the IntelliJ window. Here's what the difference looks like:
<br />
For instructions on how set this up, please see **[this part](https://docs.cs200.io/s/java-stencil-setup-guide#Opening-a-Stencil-in-IntelliJ)** of the **[Java Stencil setup guide](https://docs.cs200.io/s/java-stencil-setup-guide)**.
<br />
<details> <summary>Why the difference?</summary>
Each CS200 stencil contains some settings files that tell IntelliJ how to run our code (e.g., which subfolders contain the code, where to find the libraries, etc)--you can see the settings on Github in the `.idea` directory. IntelliJ looks for the settings in the top-level folder only, it will only see them if you open the project folder at the top-level. This may be annoying, but once you do it, you shouldn't need to configure any other settings in IntelliJ, so everything else should work!
</details>
:::
## Style Expectations
While you may have seen references to the course style guide, for this first assignment **we'll only be expecting the following style requirements**:
- Basic Javadocs for all methods (you can look in the class notes for examples of these)
- Method and variable names are in `camelCase`
- Class names are in `UpperCamelCase`
## Testing Guide in Java
In this assignment, you will be asked to develop some tests for your methods. For guidance on how to test using JUnit in Java and create thorough tests, please refer to the [Testing Guide](https://docs.cs200.io/java-testing-guide). We **strongly recommend** reading this guide before starting tests.
## 🚨 Super Important Notes 🚨
Since this is our first assignment, our autograder needs to be set up a bit differently than usual and has a few extra requirements. To be consistent with our autograder, you must follow a few conventions (just for HW1):
- **If we ask you to make fields in a class, make them `public`**: That is, if you were creating a field called `length`, you should declare it as `public int length`, similar to what we did in class.
- **Naming**: If the handout asks you to create a field or method, give it **exactly** the same names as listed in this handout. Our autograder will try and access fields with these names—if you don't use them, there will be errors! You are free to use whatever names you want if you make extra helper methods or other fields—so long as it's for something we didn't specifically ask you to write.
:::success
**What to expect in HW1**: The handout, and HW1 as a whole, guides you through developing the code in multiple stages. **You will turn in one set of files with your cumulative work on all tasks.** You do *not* need to maintain versions of your code from each task separately.
:::
***
## Horse Ancestry Trees
The goal of this section is to compare lists and trees as structures for representing [horse pedigree](https://www.pedigreequery.com/).
### Ancestor Lists
We will identify a horse by its name and its color, as represented by the following Java record:
```java
public record Horse(String name, String color) { }
```
We can also identify other information about a horse using this record:
```java
public record HorseData(Horse horse, String color, String momName, String dadName) { }
```
An example of what [Secretariat's](https://www.pedigreequery.com/secretariat) pedigree looks like as a `List` of `HorseData` is given in the `setup` method of `Homework1CTest.java`.
#### Looking Ahead
You will complete a method in `HorseUtils` called `parentOf` that takes in a horse name (as a String), a `List` of `HorseData`, and an Enum that indicates that we are searching for the mom or the dad. It should return the name of the corresponding parent, or null if the given name isn't the name of a horse in the list. You can assume that each horse in the list has a unique name.
For example:
```java
parentOf("Secretariat", horseAncestorList, Parent.mother)
```
should return `"Somethingroyal"`, and
```java
parentOf("Rose Prince", horseAncestorList, Parent.father)
```
should return `null` because there is no horse named "Rose Prince" in the data.
:::danger
**⚠️ Important Note About the Stencil ⚠️**
In the remainder of the assignment, **the stencil code we've given you might need to be edited** to make everything work here. Identifying and **fixing errors** in the stencil is part of the point of the problem!
:::
<section>
### Task 1-A
**Write a method called `testParentOf()` in `Homework1CTest.java` that tests `parentOf`.** Feel free to make use of the `horseAncestorList` that has been initialized for you, and make your own `List`s. Remember to put the `@Test` annotation before this method to indicate that it is a unit test! Make sure to refer to the [Java testing guide](https://docs.cs200.io/java-testing-guide).
:::info
**Minimum testing expectation for `parentOf`:** Make sure your tests cover both of these situations:
- A horse name that *is* in the list (you get the correct mom or dad name back).
- A horse name that is *not* in the list (you get `null` back).
(If your dataset includes a horse whose `momName` or `dadName` is `null`, it's also a good idea to test that case.)
:::
</section>
<section>
### Task 1-B
**Complete the `parentOf` method in the `HorseUtils` class and make sure your tests pass.** You can use `filter` or recursion as you wish (though we believe filter will be easier). Feel free to add more tests as you develop and test your method.
</section>
### Ancestor Trees
We can also represent a horse by its lineage by creating a binary tree, with the left and right trees representing its mother and father (note: this is like an IBinTree from Lab 2). In this case, we represent a node using `HorseNode`, using `NoHorse` to indicate when a Horse's parent is unknown.
:::info
<details>
<summary><b>Example: Pedigree</b></summary>
An example of what [Rags to Riches'](https://www.pedigreequery.com/rags+to+riches4) immediate pedigree looks like could be represented by the following tree:
```java
ragsToRichesTree =
new HorseNode(new Horse("Rags to Riches", "chestnut"),
new HorseNode(new Horse("Better Than Honour", "bay"),
new NoHorse(), new NoHorse()),
new HorseNode(new Horse("A.P. Indy", "gray"),
new NoHorse(), new NoHorse()))
```
</details>
:::
You will write a `HorseNode` method called `addAncestors` that takes in a horse's name, a mother's name/color, and a father's name/color (as Strings) and returns an `IHorseTree` with the horse and its parents added to the ancestor tree. If the horse is not found in the tree, the method will return the ancestor tree unchanged. You can assume that each horse in the tree has a unique name and that each parent you are asked to add does not yet exist in the tree.
:::info
<details>
<summary><b>Example: addAncestors</b></summary>
For example:
```java
addAncestors("Better Than Honour",
"Blush With Pride", "bay",
"Deputy Minister", "chestnut")
```
would return the following tree, if we printed it out:
```
HorseNode[
horse=Horse["Rags to Riches", "chestnut"],
momTree=HorseNode[
horse=Horse["Better than Honour", "bay"],
momTree=HorseNode[
horse=Horse["Blush With Pride", "bay"], momTree=NoHorse, dadTree=NoHorse],
dadTree=HorseNode[
horse=Horse["Deputy Minister", "chestnut"], momTree=NoHorse, dadTree=NoHorse]],
dadTree=HorseNode[name=A.P. Indy, momTree=NoHorse, dadTree=NoHorse]]
```
</details>
:::
<section>
### Task 2-A
**Write a method called `testAddAncestors()` in `Homework1CTest.java` that tests `addAncestors`.** You will have to make your own example `HorseNode`s.
:::info
**Minimum testing expectation for `addAncestors`:** Make sure your tests cover both of these situations:
- The horse *is* found in the tree (the returned tree has the two parents added in the right place).
- The horse is *not* found in the tree (the method returns the original tree unchanged).
:::
:::danger
When testing, using `==` to compare `IHorseTree`s will cause your tests to fail, even if the trees look the same (we'll talk about why next week in lecture). Instead, you should use `Assert.assertEquals()` or the `.equals()` method we have provided in the stencil.
```java
// These tests work
Assert.assertEquals(myTree.addAncestors(...), expectedTree);
Assert.assertTrue(myTree.addAncestors(...).equals(expectedTree));
// This test doesn't
Assert.assertTrue(myTree.addAncestors(...) == expectedTree);
```
:::
</section>
<section>
### Task 2-B
**Complete the `addAncestors` method in the `HorseNode` class and make sure your tests pass.**
</section>
### Building Trees
We can create some methods to help us build ancestry trees.
You will also write a `HorseUtils` method called `buildHorseTree` that takes in the name of a horse and a `FuncList` of `HorseData`s and returns an `IHorseTree` of all of the horse's ancestors. If the horse is not found in the list, `buildHorseTree` should return a tree with just that horse and no parents; the horse's color should be `"unknown"`.
:::info
<details>
<summary><b>Example</b></summary>
For example, `buildHorseTree("Imperatrice", horseAncestorList)` should return the following tree:
```
HorseNode[
horse=Horse["Imperatrice", "black"],
momTree=HorseNode[
horse=Horse["Caruso", "black"],
momTree=HorseNode[horse=Horse["Sweet Music", "unknown"],
momTree=NoHorse, dadTree=NoHorse],
dadTree=HorseNode[horse=Horse["Polymelian", "unknown"],
momTree=NoHorse, dadTree=NoHorse]],
dadTree=HorseNode[horse=Horse["Cinquepace", "unknown"],
momTree=NoHorse, dadTree=NoHorse]]
```
</details>
:::
<section>
### Task 2-C
**Write a method called `testBuildHorseTree()` in `Homework1CTest.java` that tests `buildHorseTree`.**
:::info
**Minimum testing expectation for `buildHorseTree`:** Make sure your tests cover both of these situations:
- The horse name *is* in the list (you get a tree whose root horse has the correct color, and missing ancestors use `"unknown"`).
- The horse name is *not* in the list (you get a tree with just that horse, color `"unknown"`, and no parents).
:::
</section>
<section>
### Task 2-D
**Complete the `buildHorseTree` method in the `HorseUtils` class and make sure your tests pass.** It will help to make use of your `parentOf` function from Task 1.
</section>
## Runtime Comparisons
This task asks you to compare the ease of finding a horse's grandfather using a list vs. using a tree. **Write your answers for the following tasks as comments at the bottom of your `HorseUtils.java` file.**
<section>
### Task 3-A
**Imagine you were asked to write a `HorseUtils` method called `findGrandadList`** that takes in the name of a horse (as a String) and a `FuncList` of `HorseData`s and returns a String that is the name of the horse's paternal grandfather. (You can assume that the horse and the horse's father are in the list.)
**Sketch out (in a comment) roughly what the code would do**—you don't have to write this and get it running, just sketch out how you would do it.
</section>
<section>
### Task 3-B
**Imagine you were asked to write a `HorseUtils` method called `findGrandadTree`** that takes in a `HorseNode` and produces a String that is the name of the paternal grandfather of the root horse. (You can assume that the root, the dad tree, and the grandfather tree are not `NoHorse`.)
**Sketch out (in a comment) roughly what the code would do**—you don't have to write this and get it running, just sketch out how you would do it.
</section>
<section>
### Task 3-C
**Determine the [big-O runtime](https://docs.cs200.io/runtime) of each of these functions, assuming you had implemented your sketches.** Remember the cost of using helper and built-in functions.
In a comment, state each answer in big-O notation, such as O(1), O(N), O(N²), etc.
:::info
**Clarity note for runtime answers:** In your comments, explicitly say what `N` represents (for example, the number of `HorseData` entries in the list). When reasoning about runtime:
- Accessing a node's immediate fields/children in a tree is constant time.
- Searching through a list (including using `filter`) is linear in the list length.
:::
</section>
## Design Reflections
<section>
### Task 4-A
**In the comments at the bottom of `HorseUtils.java`, explain why it is possible to add a new horse that has the same name as an existing horse to a `HorseNode`, without having `findGrandadTree` break.**
Why can't you do the same thing to a `List` of `HorseData`s and have `findGrandadList` still work correctly in all cases?
</section>
<section>
### Task 4-B
**In the comments, reflect on the limitations or shortcomings of using an ancestor tree as the data structure to represent a human person's family.** This question is asking you about *ancestry* trees, which are used to represent one person's ancestors, so your answer should be something other than "this tree cannot represent siblings."
Ancestor trees are not the only way to represent lineage. You can also use *descendant* trees, where each tree can have an arbitrary number of descendants.
</section>
<section>
### Task 4-C
**In the comments, write down a `DescendantTree` record definition, where each tree has a name and links to an arbitrary number (0 or more) of descendants.**
:::success
**Hint:** Which Java data structure that you've seen can group an arbitrary number of items?
:::
</section>
## How to Hand In
:::danger
**Important: Your solution code files should be in the `sol` package.** This means that all your solution code should have a line at the top saying `package sol;` and they should be in the `sol/` directory of your project.
:::
To hand in your homework, **submit** the following files to the **Homework 1C-15: Implementation** assignment on Gradescope:
After completing this assignment, your `sol/` directory should contain the following files:
- `Homework1CTest.java` containing `public class Homework1CTest`
- `HorseUtils.java` containing `public class HorseUtils`
- `HorseNode.java` containing `public class HorseNode`
- `NoHorse.java` containing `public class NoHorse`
- `AutograderCompatibility.java` containing `public class AutograderCompatibility`
To hand in your homework, you should do the following (see the **[Gradescope submission guide](https://docs.cs200.io/gradescope-submission-guide)** for instructions):
1. Commit and push your code to your github repository. After pushing your code, you can check on github that all of the files you modified are present in the `sol` folder on Github.
2. Submit your code to the **Homework 1C-15: Implementation** assignment on Gradescope. We'll use this submission to grade your code
Once you have handed in your homework, you should receive an email, more or less immediately, confirming your turn-in.
:::warning
<details>
<summary><b>Note on Autograder Compatibility</b></summary>
There should be a class in the stencil code named `AutograderCompatibility`. Using this class is required to ensure that your submission is working correctly with the autograder. You will be penalized if your code does not work with the autograder.
If Gradescope gives you the message *"Could not run your code (0.0/0.0),"* uncomment the main method of `AutograderCompatibility` and check that it compiles and runs. If the Gradescope autograder still doesn't work, come to hours or post on Ed for help.
</details>
:::
***
## **đź’ˇApplicationsđź’ˇ**
- **Tree Data Structures:** Binary trees are fundamental in computer science, powering everything from file systems to database indexes to game AI decision trees.
- **Genealogy Software:** Real genealogy applications like Ancestry.com use tree structures to represent family relationships and enable efficient ancestor lookups.
- **Algorithm Complexity:** Comparing list vs. tree operations teaches the importance of choosing the right data structure—a skill critical for system design interviews.
- **Data Modeling:** Deciding between lists and trees based on access patterns mirrors real architectural decisions in software engineering.
- **Recursive Thinking:** Building trees recursively from flat data is a common pattern in parsing, compilers, and data transformation pipelines.
***
_Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our [anonymous feedback form](https://forms.gle/eVKnVzRa1zG365zZA)!_