{"id":784,"date":"2016-10-21T14:57:40","date_gmt":"2016-10-21T21:57:40","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=784"},"modified":"2016-10-21T14:57:40","modified_gmt":"2016-10-21T21:57:40","slug":"lecture-20161021","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc320\/2016\/10\/21\/lecture-20161021\/","title":{"rendered":"Lecture 2016\/10\/21"},"content":{"rendered":"<p>Today we move on to memoization and dynamic programming! This is a widely applicable technique that also lets us practice algorithm design and analysis, designing recursive solutions, and designing iterative solutions. Woo-hoo! \ud83d\ude42<\/p>\n<ul>\n<li>Here are <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/files\/2016\/10\/2016-10-21-dp-change.pdf\">today&#8217;s notes<\/a> (part 1 on Memoization and DP using the change example).<\/li>\n<li>For Monday, <strong>read Section 6.1<\/strong>.<\/li>\n<li>I\u00a0<strong>will<\/strong> try to post a quiz, but the UBC Survey system is crashing for me. If I cannot post it by noon on Saturday, I won&#8217;t, but <strong>please<\/strong> work the problems anyway!\n<p>Here is the quiz:<\/p>\n<ul>\n<li>The recursive solution to the weighted interval scheduling problem has to make one key\u00a0decision\u00a0among two or more choices by <strong>trying all the choices<\/strong>\u00a0and picking the best. What is the decision?\n<ul>\n<li>Which among all the previous events will\u00a0go before this event<\/li>\n<li>Whether or not to include this event in the solution<\/li>\n<li>Whether the next event&#8217;s start time is before this event&#8217;s finish time (i.e., they conflict)<\/li>\n<\/ul>\n<\/li>\n<li>How do\u00a0we figure out\u00a0that there are only n+1 total possible sub-problems in the memoized solution?\n<ul>\n<li>Because the only legal arguments to the algorithm are 0 through n.<\/li>\n<li>Because of the algorithm&#8217;s &#8220;for&#8221; loop going from 0 up to n.<\/li>\n<li>Because the algorithm runs in O(n) time.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<li>We&#8217;re working on grading the exam and will be done\u00a0soon. However, scanning\/handback is likely to take until roughly class time on Wednesday.<\/li>\n<li>There will be no quiz in next week&#8217;s class. Sorry! Too busy with exam prep\/marking to get one together \ud83d\ude41<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Today we move on to memoization and dynamic programming! This is a widely applicable technique that also lets us practice algorithm design and analysis, designing recursive solutions, and designing iterative solutions. Woo-hoo! \ud83d\ude42 Here are today&#8217;s notes (part 1 on Memoization and DP using the change example). For Monday, read Section 6.1. I\u00a0will try to &hellip; <a href=\"https:\/\/blogs.ubc.ca\/cpsc320\/2016\/10\/21\/lecture-20161021\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Lecture 2016\/10\/21&#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-784","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\/784","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=784"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/784\/revisions"}],"predecessor-version":[{"id":786,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/posts\/784\/revisions\/786"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/media?parent=784"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/categories?post=784"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc320\/wp-json\/wp\/v2\/tags?post=784"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}