## Lecture Notes 2016/09/09

Today we continue the first stable marriage handout, although we’re skipping some pieces that you have a good sense of from the reading.

I report on the pre-class quiz below. Short version: 85% of those who took the quiz earned 2/2; only 2% earned 0/2. Thanks for doing the readings!

Next time, we continue stable marriage but introduce reductions, which we’ll use frequently to relate one problem to another. (We’ll use reductions to solve new problems in terms of old ones. Intriguingly, we’ll also eventually use reductions in the opposite way: to establish that we don’t know how to (or cannot) efficiently solve new problems by relating them to—reducing to them from—old ones.)

Important notes for today:

• Come to tutorial next week prepared for your tutorial quiz. The collected quizzes, plus possibly an extra problem, will become your assignment. (We’ll post each tutorial’s quiz question as the tutorial ends so everyone can start the assignment at the same time.)
• Follow along with the worked example in the screencast (and a blank copy of the problem). I was behind on this; so, the pre-class quiz is worth full credit if you answer it at all. (Suggestion: print the blank problem and try it, but after each major section or if you’re stuck even briefly, let the screencast help! This is not the way to study for an exam, but it will prepare you for class.)
• The next pre-class quiz is due by noon on 2016/09/12 and will be e-mailed to your ugrad.cs.ubc.ca account by 5PM today. It is about the worked example. Because I was behind on posting the worked example, you get full credit on the pre-class quiz if you submit it at all. So, submit it! (Our normal pre-class quiz pace will be ~1-2 per week, but the start of term is so exciting!!)
• Also read the syllabus on the course website. Early next week we’ll have a light-weight pre-class quiz about it.
• A sample solution to the first set of notes is available.
• If you wish to read ahead, I expect us 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.

P.S. Our first pre-class quiz went well! 151 people responded (out of 187 registered and on the waitlist). Of those, 128 earned 2/2, 20 earned 1/2, and 3 earned 0/2. (The marking scheme partly responsed to how hard the questions proved to be. The scheme was more complicated than this, but I believe in the end this is also coincidentally correct: correct response to the two easiest questions (about increasing and decreasing preference orders for men and women) plus any one other earned a 2/2, correct responses to either of the easiest questions earned a 1/2. Incorrect responses to both earned a 0/2.

P.P.S. If you don’t receive next class’s pre-class quiz by the end of today, please e-mail cs320@ugrad.cs.ubc.ca with your name, student #, ugrad.cs.ubc.ca login ID, and whether you are on the waitlist or in the course.

## 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: