Protected: Tutorial #4 Sample Solutions
Enter your password to view comments.
Author Archives: Steve
Read Before 2015/02/23 Class
During Reading Break, I thought we should have some reading 🙂
Please read:
- Section 5.3
- Section 5.4
We’ll likely finish Chapter 5 at that point.
Next, we’ll either continue discussing Divide and Conquer for a while with limited new readings (perhaps one or both of the remaining sections) or we’ll move on to Chapter 6.
Since we’re definitely moving on to Chapter 6 eventually, if you want to read ahead, I recommend starting with 6.1 to 6.4 on the completely awesome topic of Memoization and Dynamic Programming.
Assignment #4
PDF document:Â Assignment #4
Due Monday 2015/02/23 at 5PM in our submission box (#32).
- Use the assignment cover page.
- Read the academic conduct guidelines or expect horrendous consequences for you.
- Please work with a partner; you’ll learn more, and we’ll spend less time on marking and more on making the course awesome.
Protected: Midterm #1 and Sample Solutions
Enter your password to view comments.
Slides #10: Divide-and-Conquer Intro w/QuickSort and Medians
Here’s PDF of the 2015/02/11 notes.
Read Before 2015/02/13 Class
- Section 5.2
- Wikipedia’s page on the Master Theorem
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.)
Read Before 2015/02/11 Class
- Chapter 5 intro
- Section 5.1
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).
Solutions to practice exam problems
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).
Protected: Assignment #3 Sample Solution
Enter your password to view comments.
Read Before 2015/02/06 Class
- Review all readings so for (Chapters 1, 2, and 3; Sections 4.1-4.7)
- At minimum read through midterm 1 practice problems (better to actually work through them!)
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).