Short Exercises #6

Due: Friday, December 2nd at 4:30pm CT

Please note the non-standard due date.

The following short exercises are intended to help you practice some of the programming concepts introduced in weeks 7 and 8. These exercises should not take more than 1–3 hours in total to complete. The goal of these exercises is to help you develop skills in writing recursive functions.

Fetching the instructor files

To get the files for this set of short exercises, first set the GITHUB_USERNAME environment variable by running the following command at the Linux command line (replacing replace_me with your GitHub username):

GITHUB_USERNAME=replace_me

(remember you can double-check whether the variable is properly set by running echo $GITHUB_USERNAME)

Then navigate to your Short Exercises repository and pull the new material:

cd ~/capp30121
cd short-exercises-$GITHUB_USERNAME
git pull upstream main

You will find the files you need in the se6 directory.

IMPORTANT: If you are unable to obtain the instructor files by running the commands above, do not try to add the files in some other way. Doing so will likely prevent you from submitting your code. Instead, please seek assistance on Ed Discussion or at office hours.

Exercises

Recursion with numbers and lists

1. Complete the function harmonic_sequence which takes an integer \(N\) and returns the sum of the first \(N\) values in the harmonic sequence. That is, it returns the sum

   \[1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{N}.\]

   This is the recursive version of harmonic_sequence from SE #5. Do not use loops, list comprehensions, or NumPy.

2. Complete the function recursive_len which takes a (possibly empty) list and returns its length, calculated recursively. For example, recursive_len([5, 4, 6]) should return 3. Do not use the len function, loops, list comprehensions, or NumPy.

Recursion with trees

Exercises 3-5 involve the Tree class. You might find it helpful to refer to this class’s attributes and methods as you work through these problems. You can find an implementation of the Tree class in tree.py.

3. Complete the function min_depth_leaf, which takes a Tree instance and returns the minimum depth of a leaf in the tree. Recall that the depth of a node is the length of the path from the root to that node. So, min_depth_leaf returns the minimum length of a path from the root to a leaf.

   For example, this tree should return 1, because there is a path of length 1 from the root of the leaf B, and this is the shortest path from the root to any leaf (the leaves in this tree are B, E, and F).

   A: 20
     │
     ├──B: 80
     │
     └──C: 50
        │
        ├──D: 110
        │  │
        │  └──F: 50
        │
        └──E: 60
   

4. Complete the function repeated_value, which takes a tree, and returns a boolean indicating whether there is a node in the tree that has the same value as one of its ancestors.

   For example, the tree above should return True, because node 'C' is an ancestor of node 'F', and both have the same value.

   On the other hand, this tree would return False, because even though node 'B' and node 'F' have the same value, one is not an ancestor of the other:

   A: 20
     │
     ├──B: 50
     │
     └──C: 80
        │
        ├──D: 110
        │  │
        │  └──F: 50
        │
        └──E: 60
   

   Recall that a recursive function to solve this problem must work not just when the input tree is the entire original tree of interest, but also when the input is a subtree of that original tree. Furthermore, if the input to the recursive function were just a tree, we would be missing information: Given only the input tree, there is no way to access information about its ancestors in the original tree. Since you would like to compare the values in the input tree to the values of its ancestors, you will want a recursive helper function with an extra parameter.

   You should write a recursive helper function repeated_value_r. This function will take in a tree t — which may be the original tree of interest, or may be a subtree thereof — as well as a set ancestor_values, which is a set of all values occurring in the original tree above t (that is, along the path that goes directly up to the root). It will return a boolean indicating whether there is a node in t that has an ancestor with the same value (this ancestor may be in t, or may be higher up in the original tree).

5. Complete the function prune_tree which takes a tree and a set of strings, keys_to_discard. This function will recursively traverse the tree, returning a copy of the original tree but with all nodes whose keys are in keys_to_discard removed, along with their descendants. Do not modify the original tree.

   For example, using the tree above, and using the set {B, D} as keys_to_discard, this function would return the following tree.

   A: 20
     │
     └──C: 80
        │
        └──E: 60
   

   Notice that nodes B and D are not in the output tree, but neither is node F, which was a descendant of node D.

   The provided tests do not include any cases where the key of the root is in keys_to_discard. You may choose what your function does in those cases.

Testing and Submitting your Solutions

Testing your solutions

Make sure to test your code as you go along; see the Testing Your Code page.

Also, check that you have used recursion in all of your solutions. Solutions that do not use recursion will not receive credit, regardless of whether the automated tests pass.

Submitting your work

Once you’ve completed the exercises, you must submit your work through Gradescope (linked from our Canvas site). Gradescope will fetch your files directly from your GitHub repository, so it is important that you remember to commit and push your work!

To submit your work, go to the “Gradescope” section on our Canvas site. Then, click on “Short Exercises #6”. Then, under “Repository”, make sure to select your uchicago-CAPP30121-aut-2022/short-exercises-$GITHUB_USERNAME.git repository. Under “Branch”, just select “main”.

Finally, click on “Upload”. An autograder will run, and will report back a score. Please note that this autograder runs the exact same tests (and the exact same grading script) described in Testing Your Code. If there is a discrepancy between the tests when you run them on your computer, and when you submit your code to Gradescope, please let us know.

Your ESNU score on this set of exercises will be determined solely on the basis of these automated tests:

Grade	Percent tests passed
Exemplary	at least 95%
Satisfactory	at least 75%
Needs Improvement	at least 50%
Unsatisfactory	less than 50%

If there is a discrepancy between the tests when you run them on your computer, and when you submit your code to Gradescope, please let us know. Please remember that you can submit as many times as you want before the deadline. We will only look at your last submission, and the number of submissions you make has no bearing on your score.