NOTE: We’re still figuring out whether we’ll separately post handouts and notes for each section or use one combined post. For now, here are handouts and notes similar to those all three sections will use tomorrow. (If we split up by section, we’ll use categories so you can just click on your section’s category to get your section’s handouts/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/winterterm22016/cpsc320/. We e-mailed the signup code to you and will give it again in class.
- Come to your registered tutorial next week (the week of Monday 9 Jan). There will be a graded quiz focused on stable marriage and algorithm/data structures review! (The small number of waitlisted students should pick a tutorial to go to and let the TA know they’re waitlisted.)
- Do the pre-class reading for 2017/01/06, which is Kleinberg and Tardos Section 1.1. (The first chapter used to be available online but seems to have been removed, unfortunately! 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!)
- Take the pre-class quiz before 10PM on 2017/01/05. The quiz invitation has been e-mailed to your @ugrad.cs.ubc.ca e-mail address and will be automatically resent at the end of the day on 4 Jan. So, configure your @ugrad.cs.ubc.ca e-mail address using https://www.cs.ubc.ca/getacct/.
- 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:
- Stable Marriage Problem Worksheet (sample solution to be posted before next class)
- How to Solve a 320 Problem
- Gale-Shapley Algorithm
- Canadian Resident Matching Service’s Match Algorithm page (more recent than the handout, though only the style has changed)
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.