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 For this problem you will again be working with a MAX-HEAP where each node has four subtrees which are less than it. Our MAX-HEAP starts out with n values in it. You are going to call HEAP::Delete() n times to remove the items from the HEAP one by one in descending order. This is the algorithm where we take the value currently in the node that needs to be removed and copy it into the root, and then "fix" the heap as needed due to this data movement. Refresh your understanding of the runtime of the Delete() method and then prove what the total cost will be to delete all of the elements from the HEAP in this manner. We care about the constants in front of the largest order term for this problem. You are looking at the number of data comparisons in the worst case if the heap starts with n values. Question #2 (wait until after Monday's lecture) Provide pseudocode for an algorithm that will alphabetically sort a list that will contain somewhere between 32,000 and 64,000 records where the person's first name is treated as the sort key, and the length of any single first name is between 3 and 9 (inclusive). Your algorithm needs to sort these in linear time in terms of memory accesses, and use at most linear temporary space. Since we've discussed that many so-called linear time sorting algorithms require clever adaptations to actually count as "linear" to us, your solution needs to make use of at least one "clever thing" that you identify for us. It doesn't have to be very clever, though I would like you to try to think of different approaches as you work on this question.