Short Exercises #6¶

Due: Friday, December 4 at 9pm 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 week 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.

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.

Exercises¶

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']
```
Find a pattern between the first and second columns above. Then, complete the function sublists, which takes a list of values and returns a list of all sublists of the input.

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 (depth was defined in the prerecorded lectures). In other words, it returns the minimum length of a path from the root to a leaf.

Complete the function repeated_value, which takes in 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, this tree would return True, because node 'C' is an ancestor of node 'F', and both have the same value:
```
A: 20
  │
  ├──B: 80
  │
  └──C: 50
     │
     ├──D: 110
     │  │
     │  └──F: 50
     │
     └──E: 60
```
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 we would like to compare the values in the input tree to the values of its ancestors, we will want a recursive helper function with an extra input.

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).

Testing and Submitting your Solutions¶

Like the previous short exercises, you will need to pull some instructor files to your repository, and then add your code to one of those files. You can find detailed instructions on how to do this in our Coursework Basics page. For instructions on how to test your code, please see our Testing Your Code

Once you’ve completed the exercises, you must submit your work through Gradescope (linked from our Canvas site). In the “Short Exercises #6” assignment, simply upload file se6.py (do not upload any other file!). Please note:

You are allowed to make as many submissions as you want before the deadline.
There are no extensions for the short exercises. The two free extensions you get for the programming assignments cannot be applied towards the short exercises. Please note that, if you need an extension due to extraordinary circumstances, you should alert us via a private message on Piazza.
Your score on the short exercises is determined solely based on the automated tests, but we may adjust your score if you attempt to pass tests by rote (e.g., by writing code that hard-codes the expected output for each possible test input).
Gradescope will report the test score it obtains when running your code. If there is a discrepancy between the score you get when running our grader script, and the score reported by Gradescope, please let us know so we can take a look at it.