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.
Category Archives: Uncategorized
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
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:
- 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.