PDF document: Assignment #4
Due Monday 2015/02/23 at 5PM in our submission box (#32).
Here’s PDF of the 2015/02/11 notes.
As you’re reading, think about how Sections 5.1 and 5.2 relate to the cases of the Master Theorem. (The same sorts of tree analyses that we and the textbook will do can also build up a proof of correctness for the Master Theorem.)
Yes, you have a midterm on the evening of the 10th. So, just skim the reading and come back to it later.
It should be largely review; pay particular attention to the section entitled “Unrolling the Mergesort Recurrence” (~1 page of reading spanning pages 212-213).
You can find all my sample solutions in my YouTube CPSC 320 playlist.
Here is the PDF of those written solutions. Be aware, however, that I generally focused more on talking through the solutions than writing them clearly; so, some solutions may make little sense without the video context.
Note that for 5.3 and 8.1 (and possibly a few others), I fell short of what I’d consider total closure on the question. 5.3 is a bit of a broken question; for 8.1, I’m satisfied with my possibly-loose answer (and wanted to move on to the more important 2nd and 3rd parts of the question).
I will also ask you to read Section 5.1 before the Wednesday 11 Feb class (just after the midterm); so, I recommend doing that reading now.
That said, the reading should be largely review; so, skim quickly, paying particular attention to the section entitled “Unrolling the Mergesort Recurrence” (~1 page of reading spanning pages 212-213).