HackMDHomework 1C (CS 15): (Neon) Trees
We will open this assignment for submission in Gradescope sometime Tuesday. We are still finishing configuring the autograder around the changed assignment contents.
Due: Friday, February 11th, 2022 at 11:59pm ET
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 functional programming. 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 assignments after we come back together will assume you can do these sorts of problems on your own.
Topic: This assignment familiarizes you with traversing tree structures and proposing datatypes for tree structures. It also has you practice analyzing runtimes.
Learning Objectives
- To practice working with tree-like datatypes in Pyret
- To practice converting lists into tree-like datatypes
- To practice runtime annotation
- To practice reasoning about design with tree-like datatypes
Setup
- Go to code.pyret.org; this requires logging in with any Google account (like your Brown account).
- Make a new file in code.pyret.org called
hw1c-15-code.arr. - Do not put your name anywhere in the file.
Before you start, paste this statement at the top of your code.
Documentation
Once you have opened the editor, the Pyret documentation is accessible from the Pyret logo button in the top left corner of code.pyret.org.
Staff Assistance
Your friendly TAs and Professors are here to help with this assignment! We monitor Ed regularly, and it's a fantastic resource! You can find our schedule for office hours here.
Black Horse and the Cherry Tree
The goal of this section is to compare lists and trees as structures for representing horse pedigree.
Ancestor lists
We will identify a horse by its name and the name of its mother and father, as represented by the following datatype:
Example pedigree list
An example of what Secretariat's pedigree looks like could be represented by the following list:
Task: copy the above datatype definition into your file. Write a function called parent-of that takes in horse name (as a String), a List of Horses, and a Boolean flag that indicates whether or not we are searching for the mom (otherwise, the dad). It should produce the name of the corresponding parent, or an empty string if the name is not found in the list. You can assume that each horse in the list has a unique name. We recommend using filter rather than recursion for this task.
For example, parent-of("Secretariat", horse-lst, true) should produce "Somethingroyal", and parent-of("Rose Prince", horse-lst, false) should produce "".
Task: write a check-block for your function, by coming up with some example lists.
Ancestor Trees
We can also represent a horse by its lineage, by linking it to the pedigree tree of its mother and father:
Example pedigree tree
An example of what Rags to Riches' immediate pedigree looks like could be represented by the following tree:
Task: copy the above datatype definition into your file. Write a function called add-ancestors that takes in a name, a mother's name, and a father's name (as Strings), and an ancestor tree (as a HorseTree) and produces a HorseTree with the horse and its parents added to the ancestor tree. If the horse is not found in the tree, you should produce 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.
For example, add-ancestors("Better Than Honour", "Blush With Pride", "Deputy Minister", rags-to-riches-ances-tree) would produce the following tree, as expanded in the Pyret right-side window:
Task: Write a check-block for your function, by coming up with example trees.
Task: write a function called build-horse-tree that takes in a name of a horse and a List of Horses and produces a HorseTree of all of the horse's ancestors. If the horse is not found in the list, it should produce a tree with just that horse and no parents.
For example, build-horse-tree("Imperatrice", horse-lst) should produce
Hint: you should make use of your parent-of function above.
Task: write a check-block for your function by coming up with example trees.
Runtime comparison
This task asks you to compare the ease of finding a horse's grandfather using a list vs. using a tree. Neither of the following functions should need to use recursion.
Task: write a function called find-grandad-lst that takes in the name of a horse (as a String) and a List of Horses and produces 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.
Task: write a function called find-grandad-tree that takes in a HorseTree 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 granfather tree are not empty-trees.
Task: annotate both functions with their runtime. Remember the cost of using helper and built-in functions. Because you are not using recursion, give the final answer in the closed form.
Design reflections
Task: In the comments, write why you could add a new horse that has the same name as an existing horse to a HorseTree, without having find-grandad-tree break. Why can't you do the same thing to a List of Horses and have find-grandad-lst still work?
Task: 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.
Who Let the Dogs Out
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: write down a DescendantTree data definition, where each tree has a name and links to an arbitrary number (0 or more) descendants.
Hint
What type(s) have we seen in Pyret that allow us to group an arbitrary number of items?
Now, we want to extend this reasoning to dog breed categories. Each category can be linked to an arbitrary number of sub-categories and/or breeds.
Task: write down a DogClassTree data definition, that allows you to distinguish between dog breeds (which are only associated with the breed name), and dog breed classes (which have a name and can be linked to an arbitrary number of breeds and/or subclasses).
Task: using your DogClassTree definition, represent the following relationship between breeds and classes of herding dogs:
Herding Dogs include the classes Welsh Corgis and Collies, and the breeds Swedish Valhund and German Shepherd. Welsh Corgis include the breeds Cardigan Welsh Corgi and Pembroke Welsh Corgi. Collies include the breeds Border Collie and Bearded Collie.
How to Hand-in
For this homework, you MUST submit your solutions in a file called: hw1c-15-code.arr
For autograder compatibility, please check that all required function names exactly match the functions named in this handout.
To hand in your solution, you must upload them to Gradescope. Do not zip or compress them. Read our Gradescope Submission Guide for help on submitting to Gradescope.
Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out the anonymous feedback from!
