{"id":2560,"date":"2018-03-16T20:33:35","date_gmt":"2018-03-17T03:33:35","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/?page_id=2560"},"modified":"2018-03-16T20:33:35","modified_gmt":"2018-03-17T03:33:35","slug":"tutorial-10-solutions","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/tutorial-10-solutions\/","title":{"rendered":"Tutorial 10 solutions"},"content":{"rendered":"\n<ol>\n<li>\n<ul>\n<li>With[i] = w<sub>i<\/sub> + Without[i-1].<\/li>\n<li>Without[i] = max { With[i &#8211; 1], Without[i-1] }.<\/li>\n<\/ul>\n<\/li>\n<li>We can prove that there is an optimal solution in which <i>N<\/i> contacts its children <i>c<sub>i<\/sub><\/i> in order of decreasing <i>R(c<sub>i<\/sub>)<\/i>. Assume without loss of generality that the children of <i>N<\/i> have been renumbered so <i>R(c<sub>1<\/sub>) &ge; R(c<sub>2<\/sub>) &ge; &#8230; &ge; R(c<sub>k<\/sub>)<\/i>.\n<p>Then <i>R(N) = max<sub>i=1 to k<\/sub> { i + R(c<sub>i<\/sub>) }<\/i> with <i>R(N) = 0<\/i> if <i>N<\/i> is a leaf.<\/li>\n<li>TQ(i) = max<sub>1 &le; j &le; i<\/sub> { TQ(j-1) + Q(y<sub>j<\/sub>, y<sub>j+1<\/sub>, &#8230;, y<sub>i<\/sub> } if i &ge; 1, with TQ(0) = 0<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>With[i] = wi + Without[i-1]. Without[i] = max { With[i &#8211; 1], Without[i-1] }. We can prove that there is an optimal solution in which N contacts its children ci in order of decreasing R(ci). Assume without loss of generality that the children of N have been renumbered so R(c1) &ge; R(c2) &ge; &#8230; &ge; &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/tutorial-10-solutions\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Tutorial 10 solutions&#8221;<\/span><\/a><\/p>\n","protected":false},"author":55633,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2560","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2560","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/users\/55633"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/comments?post=2560"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2560\/revisions"}],"predecessor-version":[{"id":2561,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2560\/revisions\/2561"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/media?parent=2560"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}