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.
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.
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!
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.
SMP Intro Worksheet Sample Solution
Here is a sample solution to the SMP/Intro worksheet.
Unit 2 Worksheet: Reductions and Stable Marriage
Here’s our next handout on reductions and stable marriage. We’ll likely start this on Wednesday or Friday.
UPDATED: WED 2018/01/10 9:30AM. If you have an old copy, just take a quick look at the extra question in Trivial/Small Instances and the figure added in Promising Approaches. All other changes are minor.
First Day Notes
Welcome to CPSC 320!
Our overall course goal is to learn about a common and important set of problem types, algorithmic solution approaches, and analysis techniques, and to gain the tools and experience necessary to judge how a new problem might fit one of these categories, how to approach solving the problem, and how to analyze and adjust your solution.
A few administrative notes for today, much longer than our usual since it’s the start of the term:
- Sign up for our Piazza discussion board at https://piazza.com/ubc.ca/winterterm22017/cpsc320/ and read the welcome post there that has other important material! You’ll need the Piazza access code, which we’ll announce each day in lecture for the first week or so.
- Get your @ugrad.cs.ubc.ca account set up. See https://www.cs.ubc.ca/getacct/.
- Come to your registered tutorial this week (3-5 Jan) for some review problems to help get you ready for CPSC 320. Next week (10-12 Jan) there will be a graded quiz focused on stable marriage and algorithm/data structures design and analysis review in tutorial!
- Do the pre-class reading for 2018/01/05, which is Kleinberg and Tardos Section 1.1. (Do get the textbook ASAP or be prepared to thoroughly study other resources on your own! Previous terms’ students have suggested that the international edition is equivalent but cheaper, although we cannot guarantee that’s true!)
- Review CPSC 221/EECE 320, especially asymptotic analysis and very high-level data structure info (binary trees, self-balancing binary trees, heaps, hash tables, etc.).
Next, here are today’s handouts:
- Slides used to introduce the course.
- Stable Marriage Problem Worksheet (sample solution to be posted later)
- How to Solve a 320 Problem
- Gale-Shapley Algorithm
- Canadian Resident Matching Service’s Match Algorithm page
- “NRMP As a Labor Market” article about the genesis of the National Resident Matching Program
Finally, if you wish to read ahead, we expect to read at least these sections in this order (changes may happen but probably not drastic ones):
- The rest of Chapter 1 (and, for every chapter we read, the chapter intro)
- Chapter 2 (largely review), with emphasis on 2.3
- Chapter 3
- Sections 4.1-4.7 of Chapter 4 (a bit of which is likely review)
- Sections 5.1-5.4 of Chapter 5, plus the Master Theorem on Wikipedia
- Sections 6.1-6.6 and 6.8 (which is likely review) of Chapter 6
- Sections 8.1-8.5, maybe 8.6, 8.7, 8.8, and 8.10 of Chapter 8. Note that 8.10 is useful to read early and reread as you work through this chapter.