Steve – Page 5 – CPSC 320

Lecture 2016/10/14

Today we continue our work on divide-and-conquer.

We continue to post blank and solved versions of the quizzes as they finish.
Don’t forget: quizzes on Monday in tutorial!
For Monday’s class, please read Section 5.4, plus the Master Theorem entry on Wikipedia.
No pre-class quiz for Monday. But if you don’t do the reading, you’ll wish you had. The Master Theorem will make your life so much easier!
There will be a midterm review session just after class today with Susanne and Raunak!
The midterm exam is coming soon (20 October). Check out our scheduling and room assignment information! Also, if you’re curious about little things like “am I allowed any notes in the exam”, you should really read the syllabus.
Unwind from the midterm with PageRank For Real with Susanne Fri 21 Oct 5-6PM near our lecture room (Swing 105); bonus points available!

Protected: Quiz 3: Wed Noon Edition

Lecture 2016/10/12

Today we move on to divide and conquer! We divide! We conquer!

Here are today’s notes on tug-o-war and median-finding.
Be sure to read the other recent posts that include blank and solved copies of the Tuesday and Wednesday quizzes.
Check out the sample solution to our clustering concluded notes.
Don’t forget: quizzes on Monday in tutorial!
For Friday’s class, please read 5.2-5.3 in the textbook.
Complete the pre-class quiz by noon on Friday.
There will be a midterm review session with Susanne and Raunak on Fri 14 Oct 5-6PM in our usual room (Swing 121).
The midterm exam is coming soon (20 October). Check out our scheduling and room assignment information! Also, if you’re curious about little things like “am I allowed any notes in the exam”, you should really read the syllabus.
Unwind from the midterm with PageRank For Real with Susanne Fri 21 Oct 5-6PM near our lecture room (Swing 105); bonus points available!

Protected: Quiz 3: Tue 1PM Edition (and important exam info)

Worked Example: Asymptotic Analysis

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!

Lecture 2016/10/07

Today we continue working on a proof that our clustering algorithm is correct.

No class or tutorials on Monday!
BUT, go to your Tuesday and Wednesday tutorials for the next quiz! (Monday tutorial students’ quiz will be on the 17th.)
For Wednesday’s class, please read 5.1 in the textbook. No pre-class quiz, however.
Midterm review session with Susanne and Raunak on Fri 14 Oct 5-6PM in our usual room (Swing 121)
PageRank For Real with Susanne Fri 21 Oct 5-6PM near our lecture room (Swing 105); bonus points available!

Protected: Assignment 2 Sample Solution

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:

2014W2 Final Exam Practice Problems, video sample solutions, and ugly (in the author’s opinion) hand-written solutions from the videos.
2014W2 Midterm #2 and a sample solution (password required!)
2014W2 Midterm #2 Practice Problems, video sample solutions, and ugly (in the author’s opinion) hand-written solutions from the videos.
2014W2 Midterm #1 (group exam version) and a sample solution (password required!)
2014W2 Midterm #1 Practice Problems, video sample solutions, and ugly (in the author’s opinion) hand-written solutions from the videos. (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).)
2014W1 First Sample Midterm #1 and its (password protected) sample solutions
2014W1 Second Sample Midterm #1 and its (password protected) sample solutions
2014W1 Sample Midterm #2 and its (password protected) sample solutions
2014W1 Sample Final Exam and its (password protected) sample solutions
Password protected 2014W1 Midterm #1 sample solution (original not available)
Password protected 2014W1 Midterm #2 sample solution (original not available)

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:

2016 Summer Term 1 (Harvey)
2015 Summer Term (Harvey)
2014 Winter Term 2 (Wolfman)
2014 Winter Term 1 (Belleville)
2014 Summer Term (Schroeder)
2013 Winter Term 2 (Belleville)
2013 Winter Term 1 (Belleville)
2012 Winter Term 2 (Meyer)
2009 Winter Term 2 (Wolfman)
2009 Winter Term 1 (Evans)

Lecture Notes 2016/10/05

Today we’ll finish working on clustering of photos!

For next time, read Sections 4.7. No pre-class quiz, however.
Here’s a set of notes to wrap up photo clustering.

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