PageRank info session and bonus problems

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).

Old Exams for Practice

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:

Lecture Notes 2016/10/03

Today we’ll continue working on clustering of photos with a graph-based approach.

  • Here is a sample solution to our pagerank/clustering notes.
  • For next time, read Sections 4.5-4.6.
  • Complete the pre-class quiz before next time (by noon on Wed 5 Oct).
  • Don’t forget next Monday (10 Oct) is Thanksgiving. No lecture or tutorial that day. (We do have a quiz next week, but the Monday group’s quiz will be at the start of the following week. More details coming soon.)
  • Just for fun: If you’re looking for implementation challenges, make an open-source web-based app for one of the problems below and post a link to the app and the source on Piazza for 1 bonus point (for an individual making a good version) or 2 bonus points per person (for a team making a very good version). (Not sure what web-based system to use or where to write it? I’m enjoying using Meteor on Cloud 9.)
    • The user uploads a set of photos and then drags a slider (or otherwise adjusts the desired number of categories) to see the photos auto-categorized into groups. (Choose and implement some good similarity metric between photos.)
    • A CPSC 320 student uses the app to learn about the random walk definition of a graph node’s PageRank. The app shouldn’t (only?) simulate the random walk for the student, but rather help the student walk through the algorithm for the random walk and understand what results it produces. (In other words, one-up my clunky slips of paper!)