The Useful Math Identities handout could be helpful in answering parts of this assignment.
This exercise asks you to think about how heaps work by developing formulas for various expressions involving heaps.
For each of the questions below, you will write your answers as a `pythonic' expression. That is, your expression will be something that can be passed in as an expression in a python program. For instance, 5 * 3 * (k - 2) would work but not 5 * 3 (k - 2). (The second expression here does not work because you cannot implicitly multiply. You need the * operator).
For the most part, the rules are similar to what counts as a valid expression in Java, but some of the function names are different. We've included all the functions we think you might need in the table below (there may be some functions in the table that are not needed).
Make sure that you use the exact letter casing as shown! The autograder is case-sensitive. Additionally, make sure to utilize the exact same variables as are given for each question.
When you are done, press the Download Answers button at the bottom of the page. That will generate a text file containing your answers. Upload that text file to the gradescope assignment box, where it will be autograded. As with Exercise 3, you will get feedback immediately on your submission, and may resubmit as many times as you wish. Your final score for this assignment is whatever gradescope displays at the deadline.
| Operator | Meaning | Example |
|---|---|---|
| +, -, *, / | Addition, subtraction, multiplication, division. Note that order of operations apply. | (5 * 4 + 3) - 5 / 2 = 20.5 |
| ** | Exponent. | (1 + 1) ** 3 = 8 |
| sqrt(x) | Takes the square root of the given value | sqrt(9)=3 |
| ceiling(x) | Returns the ceiling of this value | ceiling(5 / 2) = 3, ceiling(2.1) = 3 |
| floor(x) | Returns the floor of this value | floor(5/2) = 2, floor(2.1) = 2, floor(2.9) = 2 |
| log(x) | Takes the natural log of x. (In class, we'd call this $\ln(\cdot)$) | log(e) = 1 |
| log(x, b) | Takes the log with the given base. | log(8, 2)=3 |
| Max(a, b), Min(a b) | Takes the max and min respectively. (Note that this uses capital M) | Max(2, 4)=4, Min(2, 4)=2 |
For all problems, assume a zero-indexed heap.
We begin by considering a 3-heap (a heap where each node has a most 3 children) stored as an array. What are the indices of the parent and the $n$th child of index $k$? That is, fill in the following mathematical functions:
Generalize your solution from (a) to work for $d$-heaps in general. If a $d$-heap is stored as an array, what are the indices of the parent and children of index $k$? As before, number the children $0,\ldots,d-1$ and use $n$ to represent which child you are referring to. Fill in the following mathematical functions:
If a $d$-heap has height $h$, what is the maximum number of nodes that it can contain? What is the minimum? Give exact functions
If a $d$-heap has $n$ nodes, what will its height be? Give an exact function
Don't forget to submit your file to Gradescope!