Write clearly.
Write your name and section clearly on the top of the first page.
Scan/photograph clearly.
If we can't read it, we will grade it as incorrect.
After you finish your answers, scan or carefully photograph your answer sheets
and create a single PDF with those images to upload
to the ELMS entry.
You cannot e-mail them to me.
We may only grade some subset of these, but you are expected to do them all.
Use the techniques from class as you solve these homework problems. Question #1 Let us define a HW6 tree as one where the heights of the left and right subtrees of any given node differ by at most 6. Show all of your work in calculating the worst-case height of a HW6 tree containing n nodes. First, create a mathematical description of the tree and put a box around that equation. Second, undertake a proof using constructive induction to find the asymptotic class of the worst-case height. If a log base comes into the answer, please give that base to one decimal position of precision to the right of the decimal point. Question #2 For this problem you will be working with a MAX-HEAP where each node has four subtrees, the contents of which are all less than it. We start with an array of n values. What will the cost be to create a heap from that array if we process the array as if it were a complete quadrary tree, working bottom-up from the leaves like we saw in class on Monday? Formally work out your answer. For this problem I care about the constants in front of the largest order term. If log terms appear, identify the base of these terms. Carefully work out your answer and show your work.