{"id":2456,"date":"2018-02-09T21:52:24","date_gmt":"2018-02-10T05:52:24","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/?page_id=2456"},"modified":"2018-02-09T21:52:24","modified_gmt":"2018-02-10T05:52:24","slug":"tutorial-6-solutions","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/tutorial-6-solutions\/","title":{"rendered":"Tutorial #6 solutions"},"content":{"rendered":"<ol>\n<li>Please refer to the solutions to the week 5 tutorial questions.<\/li>\n<li>\n<ul>\n<li>Change the weights of the edges on the example as follows: w(clk, a) = w(d,e) = w(d,f) = 2, and w(clk, d) = w(a, b) = w(a, c) = 1. The proposed algorithm increases every edge weight to 2, but there was no need to change any of the weights.<\/li>\n<li>Because there is a unique path from the root of the tree to a given node <i>N<\/i>, the requirements that the resulting tree have zero skew means the subtree rooted at every node <i>N<\/i> must also have zero skew. The algorithm can thus be summarized as follows:\n<ul>\n<li>We perform a post-order traversal of the tree to compute, for each node <i>N<\/i>, the length of the longest path <i>L(N)<\/i> from <i>N<\/i> to a leaf.<\/li>\n<li>Once this computation has been performed, we adjust either the edge leading to the left child of <i>N<\/i>, or the edge leading to its right child, to eliminate the skew in <i>N<\/i>&#8216;s subtree.<\/li>\n<\/ul>\n<p>Here is pseudo-code for the algorithm; let us denote by <i>l(N1, N2)<\/i> the length of the edge that connects two nodes <i>N1<\/i>, <i>N2<\/i> of the tree. We can store the values <i>L[?]<\/i> in a dictionary, or as an additional field inside the nodes.<\/p>\n<pre>Algorithm adjustSkew(N)\r\n    L[N] \u2190 0\r\n\r\n    if N has a left child LN then\r\n        adjustSkew(LN)\r\n        L[N] \u2190 L[LN] + l(N, LN)\r\n\r\n    if N has a right child RN then\r\n        adjustSkew(RN)\r\n        L[N] \u2190 max { L[N], L[RN] + l(N, RN) }\r\n\r\n    if N has two children LN, RN then\r\n        l(N, LN) \u2190 L[N] - L[LN]\r\n        l(N, RN) \u2190 L[N] - L[RN]\r\n<\/pre>\n<\/li>\n<\/ul>\n<\/li>\n<li>The trick is to notice that people who know less than five other people can not be part of the subset Alice wants, nor can people who know at least <i>n-5<\/i> other people. So the algorithm is the following:\n<pre>Algorithm PickSubset(S)\r\n    while an element x of S knows fewer than 5 or more than |S| - 5 people\r\n        remove x from S\r\n    endwhile\r\n\r\n    return S\r\n<\/pre>\n<p>Note that when we write &#8220;knowing fewer than 5 or more than <i>|S| &#8211; 5<\/i> people&#8221;, we mean with respect to the current set <i>S<\/i>, not the set the algorithm started with.<\/p>\n<p><b>Proof of correctness<\/b> (not required for the tutorial): Let <i>S<sub>i<\/sub><\/i> denote the set <i>S<\/i> at the end of the <i>i<\/i>th iteration of the <tt>while<\/tt> loop. We prove by induction on <i>i<\/i> that the optimal solution to Alice&#8217;s problem is a subset of <i>S_i<\/i>.<\/p>\n<p>The base case is the case <i>i = 0<\/i>, before the first iteration of the <tt>while<\/tt> loop. At that point, <i>S<sub>0<\/sub><\/i> contains every person Alice has to choose from, and hence contains every member of the optimal solution.<\/p>\n<p>Let us now consider the induction step. Suppose the statement was true after the <i>i<\/i>th iteration of the loop, and consider now the set <i>S<sub>i+1<\/sub><\/i>. A person <i>x<\/i> removed from <i>S<sub>i<\/sub><\/i> to obtain <i>S<sub>i+1<\/sub><\/i> either knows fewer than 5 other people in <i>S<sub>i<\/sub><\/i>, which means he\/she does not know enough people in the optimal subset to be invited, or he\/she knows more than <i>|S<sub>i<\/sub>| &#8211; 5<\/i> people in <i>S<sub>i<\/sub><\/i>, which means there are not enough people in the optimal subset that he\/she does not know. In both cases <i>x<\/i> can not be part of the optimal solution, and hence the optimal solution must also be a subset of <i>S<sub>i+1<\/sub><\/i>.<\/p>\n<p>This completes the induction step. Now, when the <tt>while<\/tt> loop finally exits after <i>t<\/i> iterations, every person in <i>S<sub>t<\/sub><\/i> knows at least <i>5<\/i> other people, and there are at least <i>5<\/i> other people that he\/she does not know. Hence either <i>S<sub>t<\/sub><\/i> is empty, or it is a possible solution to Alice&#8217;s problem. Because we proved that the optimal solution is a subset of <i>S<sub>t<\/sub><\/i>, this means that <i>S<sub>t<\/sub><\/i> is the optimal solution we were looking for.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Please refer to the solutions to the week 5 tutorial questions. Change the weights of the edges on the example as follows: w(clk, a) = w(d,e) = w(d,f) = 2, and w(clk, d) = w(a, b) = w(a, c) = 1. The proposed algorithm increases every edge weight to 2, but there was no need &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/tutorial-6-solutions\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Tutorial #6 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-2456","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2456","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=2456"}],"version-history":[{"count":2,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2456\/revisions"}],"predecessor-version":[{"id":2459,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2456\/revisions\/2459"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/media?parent=2456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}