{"id":1065,"date":"2017-01-06T08:55:06","date_gmt":"2017-01-06T15:55:06","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/?p=1065"},"modified":"2017-01-06T12:14:03","modified_gmt":"2017-01-06T19:14:03","slug":"notes-for-20170106","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/2017\/01\/06\/notes-for-20170106\/","title":{"rendered":"Notes for 2017\/01\/06"},"content":{"rendered":"<article id=\"post-555\" class=\"post-555 post type-post status-publish format-standard hentry category-handouts category-readings category-uncategorized\">\n<div class=\"entry-content\">\n<p>Today we continue the first stable marriage handout, although we may skip some pieces\u00a0that you\u00a0have a good sense of from the reading.<\/p>\n<p>Brief notes on the pre-class quiz:\u00a0The vast majority of students who took the quiz will earn\u00a02\/2. (We&#8217;re downweighting the hardest question, which (CORRECTION) just over half of students got correct: &#8220;Independent of execution order, with the same preference lists, a particular man always proposes to the exact same number of women.&#8221;) Thanks for doing the readings!<\/p>\n<p>Next time, we expect to continue stable marriage but introduce <em>reductions<\/em>, which we\u2019ll use frequently\u00a0to relate one problem to another. (We\u2019ll use reductions to solve new problems in terms of old ones. Intriguingly, we\u2019ll\u00a0<strong>also<\/strong>\u00a0eventually use reductions in the opposite way: to establish that we don\u2019t 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 will become your assignment. (We\u2019ll post each tutorial\u2019s 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\/cpsc3202016w1\/files\/2016\/09\/2016-09-10-worked-example-reductions-pre-class.pdf\">blank copy of the problem<\/a>). (Suggestion: print the blank problem and try it, but after each major section or if you\u2019re 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 10PM (CORRECTED!) on 2017\/01\/08<\/strong>\u00a0and will be e-mailed to your ugrad.cs.ubc.ca account by 5PM\u00a0today. It is\u00a0about the worked example. (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\/cpsc3202016w2\/syllabus\/\">syllabus<\/a><\/strong> on the course website. Early next week we\u2019ll have a light-weight pre-class quiz about it.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<\/div>\n<\/article>\n<article id=\"post-540\" class=\"post-540 post type-post status-publish format-standard hentry category-handouts category-readings category-uncategorized\">\n<div class=\"entry-content\"><\/div>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Today we continue the first stable marriage handout, although we may skip some pieces\u00a0that you\u00a0have a good sense of from the reading. Brief notes on the pre-class quiz:\u00a0The vast majority of students who took the quiz will earn\u00a02\/2. (We&#8217;re downweighting the hardest question, which (CORRECTION) just over half of students got correct: &#8220;Independent of execution &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/2017\/01\/06\/notes-for-20170106\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Notes for 2017\/01\/06&#8221;<\/span><\/a><\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[318531,99],"tags":[],"class_list":["post-1065","post","type-post","status-publish","format-standard","hentry","category-handouts","category-readings"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/posts\/1065","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/users\/7560"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/comments?post=1065"}],"version-history":[{"count":4,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/posts\/1065\/revisions"}],"predecessor-version":[{"id":1070,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/posts\/1065\/revisions\/1070"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/media?parent=1065"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/categories?post=1065"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/tags?post=1065"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}