I’ve written an overview of how some tools in combinatorics work, such as permutations, combinations and binomial coefficients. Reading the document may be useful if you’ve had trouble in previous classes counting the size of a possible solution space, when given asked to use a brute force approach.
Today we move on to divide and conquer! We divide! We conquer!
I’ve posted a video walkthrough of working a (terribly artificial) asymptotic analysis of pseudocode problem: Asymptotic Analysis Worked Example.
This isn’t required viewing, and I won’t have a reading quiz on it, but you should feel free to use it as needed!
Today we continue working on a proof that our clustering algorithm is correct.
If you’re interested in learning about how the PageRank algorithm actually works, I’ll be holding a session about it on Friday 21 October from 5-6 pm in Swing 105.
I’ve also written a tutorial that you can look over if you can’t make the session, or if you’re interested in reading up on this earlier. There are two problems at the end that can earn you up to 3 bonus points: you can submit your solutions to me anytime before the final exam (date TBD).
Here are some old exams and sample exams (from previous terms).
Several caveats apply: In many cases these are not my exams. I do not have additional materials related to these exams that might be missing. I have not recently reviewed these, and I don’t know how well they relate to what we’ve done so far.
(I can say that we have not yet discussed decision-theoretic lower bounds and may not do so, although many of you likely saw Ω(n lg n) bound on sorting by comparisons in CPSC 221, which is a decision-theoretic lower bound.)
Some of these require the login “cpsc320” and the solutions password for our course to access, which is posted on Piazza:
Old samples I found through online searches:
Old course offerings are often available at http://www.ugrad.cs.ubc.ca/~cs320/YYYYSP, where YYYY is the 4-digit year, S is the session (W or S), and P is the part (1 or 2, often missing in summer). Here’s a few:
Today we’ll finish working on clustering of photos!