Lecture notes 2016/09/07

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:

• Sign up for our Piazza board at https://piazza.com/ubc.ca/winterterm12016/cpsc320/. I’ll give the signup code in class and also e-mailed it to registered students ~1 week before the term.
• Come to your registered tutorial next week (the week of Monday 12 Sep). 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 2016/09/09, which is Kleinberg and Tardos Section 1.1. (Note that the first chapter of the textbook is available online, but get the textbook ASAP or be prepared to thoroughly study other resources on your own!)
• Take the pre-class quiz before noon on 2016/09/09. The quiz invitation will be (automatically) e-mailed to your @ugrad.cs.ubc.ca e-mail address at the end of today’s lecture.
• Fill out the optional start-of-term survey (by the add/drop deadline) to help me learn a bit more about you and help the department learn about our courses. It’s worth 2 bonus points!
• 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.).
• If you’re not really planning to take the course, drop it! We enlarged the class to bring the waitlist down, but there are still more people to get in!

Finally, here are today’s notes:

• Stable Marriage Problem Worksheet
• Sample solution to SMP Worksheet
• 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)