{"id":2479,"date":"2018-02-26T14:09:14","date_gmt":"2018-02-26T22:09:14","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/?page_id=2479"},"modified":"2018-03-01T16:44:37","modified_gmt":"2018-03-02T00:44:37","slug":"sample-problems-for-tutorial-week-8","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/sample-problems-for-tutorial-week-8\/","title":{"rendered":"Sample problems for tutorial week #8"},"content":{"rendered":"<ol>\n<li>King Y\u00e9m\u00e9chan has given his royal mathematician Ys\u00e9conth\u00e9 a list of treasures that belong to neighbouring countries. For each treasure, the list specifies\n<ul>\n<li>How much the treasure is worth.<\/li>\n<li>How easy it would be for Yprantou (the royal thief) to <em>acquire<\/em> this treasure.<\/li>\n<\/ul>\n<p>Each treasure can thus be represented by a point in the plane: the <em>x<\/em> coordinate represents how much the treasure is worth, and the <em>y<\/em> coordinate is the difficulty of stealing that treasure (where a higher <em>y<\/em> coordinate corresponds to a treasure that is easier to steal). Given two such points, we will say that a point <em>q = (q.x, q.y)<\/em> <strong>dominates<\/strong> the point <em>p = (p.x, p.y)<\/em> if <em>q.x \u2265 p.x<\/em> and <em>q.y \u2265 p.y<\/em>. That is, <em>q<\/em> lies to the right of and above <em>p<\/em>, as illustrated in picture on the left.<\/p>\n<p>Clearly, a point <em>p<\/em> that is dominated by a point <em>q<\/em> is of no interest, since <em>q<\/em> is both worth more and easier to steal than <em>p<\/em>. Hence, to help you reach a decision, you only need to worry about locations that correspond to <strong>maximal<\/strong> points: those that no other point dominates. For instance, in the picture on the right, the points <em>p<sub>3<\/sub><\/em>, <em>p<sub>4<\/sub><\/em> are <em>p<sub>6<\/sub><\/em> are maximal, as you can see from the fact that their upper-right quadrants are empty.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/files\/2018\/02\/domination.png\" width=\"800px\" \/><\/p>\n<ol type=\"a\">\n<li>Describe a simple algorithm that takes as input a set <em>P<\/em> of points, and a point <em>q<\/em>, and returns all points of <em>P<\/em> that <em>q<\/em> does not dominate.<\/li>\n<li>Describe an efficient divide-and-conquer algorithm that takes as input a set <em>P<\/em> of points, and returns the list of treasures that Yprantou might be asked to steal first (that is, all maximal points of <em>P<\/em>). Hints:\n<ul>\n<li>Start by deciding how many subproblems you will have, and which point(s) will belong to each subproblem. You can not simply assign points to the subproblems randomly.<\/li>\n<li>If a point is maximal in one subproblem, is it automatically maximal in <em>P<\/em>? Does it matter which subproblem the point belongs to?<\/li>\n<li>When you are combining the solutions to your subproblems, you should choose a point carefully in one subproblem, and then call your algorithm from part (a) exactly once.<\/li>\n<\/ul>\n<\/li>\n<li>Analyze the worst-case running time of your algorithm from (b).<\/li>\n<\/ol>\n<\/li>\n<li>Prove upper and lower bounds on the function <i>T(n)<\/i> defined by <i>T(n) = T(\u230a4n\/5\u230b) + 2T(\u230a2n\/5\u230b) + T(\u230an\/5\u230b) + 2n<sup>2<\/sup><\/i> when <i>n \u2265 5<\/i>, with <i>T(1) = T(2) = T(3) = T(4) = 1<\/i>.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>King Y\u00e9m\u00e9chan has given his royal mathematician Ys\u00e9conth\u00e9 a list of treasures that belong to neighbouring countries. For each treasure, the list specifies How much the treasure is worth. How easy it would be for Yprantou (the royal thief) to acquire this treasure. Each treasure can thus be represented by a point in the plane: &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/sample-problems-for-tutorial-week-8\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Sample problems for tutorial week #8&#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-2479","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2479","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=2479"}],"version-history":[{"count":6,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2479\/revisions"}],"predecessor-version":[{"id":2496,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2479\/revisions\/2496"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/media?parent=2479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}