{"id":1381,"date":"2017-03-07T12:00:17","date_gmt":"2017-03-07T20:00:17","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/?p=1381"},"modified":"2017-03-08T12:34:41","modified_gmt":"2017-03-08T20:34:41","slug":"handouts-and-notes-for-20170308","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/2017\/03\/07\/handouts-and-notes-for-20170308\/","title":{"rendered":"Handouts and Notes for 2017\/03\/08"},"content":{"rendered":"<p>There&#8217;s still more to do with dynamic programming. The recurrence relation we used to describe the number of coins needed to make n cents of change had just one parameter (and so a one-dimensional table\/array), but our recurrence relations\/recursive functions can have more parameters.<\/p>\n<p>Memoization\/DP can still work. We may need a table with more dimensions. In fact, we can in general use a hash table where the key is a tuple of the parameter values.<\/p>\n<p>Off we go to the Longest Common Subsequence, then!<\/p>\n<ul>\n<li>Here are the new <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/files\/2017\/03\/2017-03-06-dp-lcs.pdf\">DP in 2-D notes<\/a> for today.<\/li>\n<li>For next class, please <strong>read section 6.5<\/strong> in the textbook. (No reading quiz, however.)<\/li>\n<li>Keep going on the <strong>assignment due Friday<\/strong>!<\/li>\n<li>Also, here&#8217;s <a href=\"http:\/\/www.ugrad.cs.ubc.ca\/~cs320\/2016W2\/memoize.rkt\">auto-memoizing code in Racket<\/a> (actually using CPSC 311&#8217;s PLAI language variant, but other than the testing framework, most of it should transfer to plain Racket) and a <a href=\"https:\/\/docs.python.org\/3\/library\/functools.html#functools.lru_cache\">built-in auto-memoizing decorator in Python<\/a>.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>There&#8217;s still more to do with dynamic programming. The recurrence relation we used to describe the number of coins needed to make n cents of change had just one parameter (and so a one-dimensional table\/array), but our recurrence relations\/recursive functions can have more parameters. Memoization\/DP can still work. We may need a table with more &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/2017\/03\/07\/handouts-and-notes-for-20170308\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Handouts and Notes for 2017\/03\/08&#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-1381","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\/1381","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=1381"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/posts\/1381\/revisions"}],"predecessor-version":[{"id":1393,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/posts\/1381\/revisions\/1393"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/media?parent=1381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/categories?post=1381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202016w2\/wp-json\/wp\/v2\/tags?post=1381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}