Here’s a worksheet to explore how Google’s PageRank algorithm came into being. (Though note that PageRank predates Twitter.)
Asymptotic Analysis Sample Solution
Here is a sample solution to our asymptotic analysis worksheet. Take a look at it and be sure you understand where the solutions came from and how they relate to the work you did!
You may also be interested in this video worked example of asymptotic analysis if you haven’t already seen it.
Readings for 2018/02/04
Before Sunday’s pre-class quiz: Read sections 4.2 or 4.3 (your choice, though many of you may have already read 4.2!) and section 4.4. If you decide to read section 4.3, you may want to also look at this document that provides examples illustrating the five cases in the proof of Theorem 4.12.
Assignment #2
UPDATES:
- 2018/01/26 7:30PM, Problem 3.3 cut from the assignment.
- 2018/01/27 9:30AM, Quiz 6.1 answer is sometimes not always
- 2018/01/27 5:00PM, Quiz 5, second-to-last comparison (with k^3 + m lg m) should be LEFT rather than SAME
- 2018/01/27 7:00PM, Problem 6: a cycle cannot contain only one vertex, and cannot repeat edges (so aba is not a cycle).
Here is the full assignment version of Assignment #2. (Here is the LaTeX source. It has a “.txt” extension because blogs.ubc.ca doesn’t allow upload of “.tex” files.)
This is due Monday 5 Feb at 10PM. (As always, we will release the solution shortly afterward. That’s especially important here if you want to peruse the solution before the exam!)
Please submit it on GradeScope.
For reference, here are the collected quizzes and the collected quizzes with sample solutions.
Old Exams for Practice
As our midterm exam approaches, here are some old exams and sample exams (from previous terms).
Several caveats apply: Our term’s exams and course may differ from these term’s exams and courses in important ways (beyond, obviously, the specific questions used!). We do not have additional materials related to these exams that might be missing. We have not recently reviewed these, and we don’t know how well they relate to what our term has done so far.
Some of these require the login “cpsc320” and the solutions password for our term or a previous one to access, which are posted on Piazza:
- 2017W2
- 2017W1 midterm 2 blank (time limit was 65 mins) and sample solution
- 2017W1 midterm 1 blank (time limit was 65 mins) and sample solution
- 2017W1
- 2017W1 final exam pre-reading and sample solution to pre-reading problem.
- 2017W1 midterm2 blank (time limit was 75 mins) and sample solution
- 2017W1 midterm1 blank (time limit was 75 mins) and sample solution
- 2016W2
- 2016W2 Final Exam with (password protected) ugly handwritten sample solution (CORRECTION: Q8.2’s i <= floor(n/2) in isMajority should be i <= ceil(n/2)).
- 2016W2 Midterm Exam (time limit was 75 mins) and sample solution (CORRECTION: Q4.3(b) “O(n + n)” should be “O(n + n lg n)”).
- 2016W1 Midterm Exam and sample solution.
- 2014W2
- 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
- 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 Winter Term 2 (Wolfman)
- 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)
Graph “Play” Worksheet
Here’s a worksheet to play around with definitions on graphs. Neither articulation points nor diameter are absolutely critical definitions, but they make good, novel definitions to explore and experiment with to understand graphs and graph terminology.
Protected: Assignment #1 Sample Solution
Resident-Hospital Matching Problem Sample Solution
Here is a sample solution to the RHP worksheet. Take a look at it and be sure you understand where the solutions came from and how they relate to the work you did!
Readings for 2018/01/28
Before Sunday’s pre-class quiz: Read sections 3.5, 3.6, 4.1, and 4.2. This will start you in on greedy algorithms. Note that we’ll start working (in the week after this pre-class quiz) on greedy algorithms via a graph example, bridging the graphs and greedy algorithms sections.
Asymptotic Analysis Worksheet
Here’s a worksheet to briefly discuss asymptotic analysis, considering both comparison of growth rates of functions and analysis of algorithms. We’ll start in on this worksheet soon, and we may move through it very quickly.
Also, here’s a one-pager to review big-O notation, add little-o notation, and offer a way that limits can help you with these comparisons.