Short Exercises #6¶

Due: Friday, December 3rd at 4:30pm CST

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–2 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 ~/cmsc12100
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¶

You must use recursion on every one of these exercises. Some of these problems may have reasonable non-recursive solutions, but the point of these exercises is to practice with recursion.

Recursion with numbers and lists¶

Complete the function sum_cubes, which takes an integer $n$ and computes the sum

\[1^3 + 2^3 + 3^3 + \dots + n^3.\]

Do not use loops nor list comprehensions.
A sublist of a list lst is a list that contains some (possibly all or none) of the elements of lst, in the same order. For example, the following are all the sublists of ['A', 'B', 'C']:
```
[]                  ['A']
['C']               ['A', 'C']
['B']               ['A', 'B']
['B', 'C']          ['A', 'B', 'C']
```
You will complete the function sublists, which takes a list of values and returns a list of all sublists of the input.

To figure out how to solve the sublists problem recursively, focus on the example above, which shows the solution to the sublists problem on the input ['A', 'B', 'C']. Identify how the first column above is the solution to the sublists problem on a simpler input. Then, find a relationship between the first column and the second column.

Recursion with trees¶

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 would return 1, because there is a path of length 1 from the root to 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
```
Complete the function prune_tree which takes in 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: 50
     │
     └──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-cmsc12100-aut-21/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%
Ungradable	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.