<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 2025)
**Due: Friday, February 7 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
### Stencil Code and Assignment Setup
Using this **[GitHub Classroom link](https://classroom.github.com/a/RRBin6OG)**, 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.
:::info
<details><summary>Click here if you encounter errors about missing jar files when opening the stencil</summary>
If you receive errors about this, you may need to add both the hamcrest-core-1.3.jar and junit-4.13.2.jar files as dependencies to your IntelliJ project. If you’re not sure how to do this, check out the [Adding Jars/Dependencies](https://docs.cs200.io/s/intellij-guide#Only-if-necessarynbsp-adding-JarsDependencies) section of the IntelliJ Setup Guide.
</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 tets, please refer to the [Testing Guide](https://docs.cs200.io/java-testing-guide). We **strongly recommend** reading this guide before starting tests.
### :rotating_light: Super important notes :rotating_light:
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
### :warning: :warning: :warning: **SUPER IMPORTANT NOTE** :warning: :warning::warning:
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 setup is part of the point of the problem!
:::
### 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 `Lists`. 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).
### 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.
## 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><i>Example:</i> 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><i>Example:</i> addAncestors</b></summary>
For example,
```
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>
### Task 2-A
**Write a method called `testAddAncestors()` in `Homework1CTest.java` that tests `addAncestors`**. You will have to make your own example `HorseNode`s.
### Task 2-B
**Complete the `addAncestors` method in the `HorseNode` class and make sure your tests pass.**
## 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><i>Example</i></b></summary>
For example, `buildHorseTree("Imperatrice", horseAncestorList)` should return the following tree:
```
HorseNode[
horse=new Horse[“Imperatrice”, “black”],
momTree=HorseNode[
horse=new Horse[“Caruso”, “black”],
momTree=HorseNode[horse=new Horse[“Sweet Music”, “unknown”,
momTree=NoHorse, dadTree=NoHorse],
dadTree=HorseNode[horse=new Horse[“Polymelian”, “unknown”], momTree=NoHorse, dadTree=NoHorse]],
dadTree=HorseNode[horse=new Horse[“Cinquepace”, “unknown”], momTree=NoHorse, dadTree=NoHorse]]
```
</details>
:::
### Task 2-C
**Write a method called `testBuildHorseTree()` in `Homework1CTest.java` that tests `buildHorseTree`.**
### 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.
# Runtime Comparisons
This task asks you to compare the ease of finding a horse’s grandfather using a list vs. using a tree. Make your comments for the following tasks at the bottom of your **`HorseUtils`** file.
### 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 `HorseDatas` 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.
### 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.
### 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), (N^2^), etc.
# Design reflections
### Task 4-A
**In the comments, 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 Parentages and have `findGrandadList` still work correctly in all cases?
### 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.
### 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?
:::
# How to Hand In
To hand in your homework, **submit** the following files to the **Homework 1C-15: Implementation** assignment on Gradescope (make sure to exclude the `AutograderCompatibility.java` file from your submission):
- `Homework1CTest.java` containing `public class Homework1CTest`
- `HorseUtils.java` containing `public class HorseUtils`
- `HorseNode.java` containing `public class HorseNode`
- `NoHorse.java` containing `public class NoHorse`
Once you have handed in your homework, you should receive an email, more or less immediately, confirming your turn-in.
:::info
<details><summary><b><i>Note:</i> 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>
***
</details>
:::
_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/SiWG5qQ4myZ1HqTM9)_!_