{"id":555,"date":"2016-09-09T15:41:36","date_gmt":"2016-09-09T22:41:36","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=555"},"modified":"2016-09-10T13:39:44","modified_gmt":"2016-09-10T20:39:44","slug":"lecture-notes-20160909","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc320\/2016\/09\/09\/lecture-notes-20160909\/","title":{"rendered":"Lecture Notes 2016\/09\/09"},"content":{"rendered":"<p>Today we continue the first stable marriage handout, although we&#8217;re skipping some pieces\u00a0that you\u00a0have a good sense of from the reading.<\/p>\n<p>I report on\u00a0the pre-class quiz below. Short version: 85% of those\u00a0who took the quiz earned 2\/2; only 2% earned 0\/2. Thanks for doing the readings!<\/p>\n<p>Next time, we\u00a0continue stable marriage but introduce <em>reductions<\/em>, which we&#8217;ll use frequently\u00a0to relate one problem to another. (We&#8217;ll use reductions to solve new problems in terms of old ones. Intriguingly, we&#8217;ll\u00a0<strong>also<\/strong>\u00a0eventually use reductions in the opposite way: to establish that we don&#8217;t know how to (or cannot) efficiently solve new problems by relating them to\u2014reducing to them\u00a0<em>from<\/em>\u2014old ones.)<\/p>\n<p>Important notes for today:<\/p>\n<ul>\n<li><strong>Come to tutorial next week<\/strong> prepared for your tutorial quiz. The collected quizzes, plus possibly an extra problem, will become your assignment. (We&#8217;ll post each tutorial&#8217;s quiz question as the tutorial ends so everyone can start the assignment at the same time.)<\/li>\n<li><strong>Follow along with the worked example\u00a0<\/strong>in the\u00a0<a href=\"https:\/\/www.youtube.com\/playlist?list=PLpdsoCzoYBF8uaLD4g7phC4DqpBa3nAfE\">screencast<\/a>\u00a0(and\u00a0a <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/files\/2016\/09\/2016-09-10-worked-example-reductions-pre-class.pdf\">blank copy of the problem<\/a>). 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&#8217;re stuck <em>even briefly<\/em>, let the screencast help! This is\u00a0<em>not<\/em> the way to study for an exam, but it will\u00a0prepare you for class.)<\/li>\n<li><strong>The next pre-class quiz is due by noon on 2016\/09\/12<\/strong> and will be e-mailed to your ugrad.cs.ubc.ca account by 5PM\u00a0today. It is\u00a0about the worked example. <strong>Because I was\u00a0behind on posting the worked example, you get full credit on the pre-class quiz if you submit it at all.<\/strong> So, submit it!\u00a0(Our normal pre-class quiz pace will be ~1-2 per week, but the start of term is so exciting!!)<\/li>\n<li><strong>Also read the <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/syllabus\/\">syllabus<\/a><\/strong> on the course website. Early next week we&#8217;ll have a light-weight pre-class quiz about it.<\/li>\n<li><strong>A <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/files\/2016\/09\/2016-09-07-notes-sample-solution.pdf\">sample solution to the first set of notes<\/a><\/strong>\u00a0is\u00a0available.<\/li>\n<li><strong>If you wish to read ahead, I expect us to read at least these sections<\/strong>\u00a0in this order (changes may happen but probably not <em>drastic<\/em> ones):\n<ul>\n<li>The rest of Chapter 1 (and, for every chapter we read, the chapter intro)<\/li>\n<li>Chapter 2 (largely review), with emphasis on 2.3<\/li>\n<li>Chapter 3<\/li>\n<li>Sections 4.1-4.7 of Chapter 4 (a bit\u00a0of which is likely review)<\/li>\n<li>Sections 5.1-5.4 of Chapter 5, plus\u00a0the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Master_theorem\">Master Theorem<\/a>\u00a0on Wikipedia<\/li>\n<li>Sections 6.1-6.6 and 6.8 (which is likely review) of Chapter 6<\/li>\n<li>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.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>P.S. Our first pre-class quiz went well! 151 people responded (out of 187 registered and on the waitlist). Of those, 128 earned\u00a02\/2, 20 earned\u00a01\/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>\n<p>P.P.S.<strong> If you don&#8217;t receive next class&#8217;s pre-class quiz by the end of today<\/strong>, 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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today we continue the first stable marriage handout, although we&#8217;re skipping some pieces\u00a0that you\u00a0have a good sense of from the reading. I report on\u00a0the pre-class quiz below. Short version: 85% of those\u00a0who took the quiz earned 2\/2; only 2% earned 0\/2. Thanks for doing the readings! Next time, we\u00a0continue stable marriage but introduce reductions, which &hellip; <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/2016\/09\/09\/lecture-notes-20160909\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Lecture Notes 2016\/09\/09&#8221;<\/span><\/a><\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[318531,99],"tags":[],"class_list":["post-555","post","type-post","status-publish","format-standard","hentry","category-handouts","category-readings"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/555","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/users\/7560"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/comments?post=555"}],"version-history":[{"count":7,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/555\/revisions"}],"predecessor-version":[{"id":576,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/555\/revisions\/576"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/media?parent=555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/categories?post=555"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/tags?post=555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}