{"id":2506,"date":"2018-03-02T22:27:18","date_gmt":"2018-03-03T06:27:18","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/?page_id=2506"},"modified":"2018-03-02T22:27:18","modified_gmt":"2018-03-03T06:27:18","slug":"tutorial-8-solutions","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/tutorial-8-solutions\/","title":{"rendered":"Tutorial #8 solutions"},"content":{"rendered":"
    \n
  1. \n
      \n
    1. \n
      Algorithm UndominatedPoints(P, q)\r\n  S \u2190 { }\r\n  for each point p of P do\r\n    if q.x < p.x or q.y < p.y then\r\n      add p to S\r\n  return S\r\n<\/pre>\n<\/li>\n
    2. \n
      Algorithm MaximalPoints(P)\r\n  sort P by increasing x-coordinate\r\n  return MaximalPointsHelper(P, 0, length[P]-1)\r\n\r\nAlgorithm MaximalPointsHelper(P, first, last)\r\n  if first = last then\r\n    return { P[first] }\r\n\r\n  mid \u2190 \u230a(first + last)\/2\u230b\r\n  Sl \u2190 MaximalPointsHelper(P, first, mid)\r\n  Sr \u2190 MaximalPointsHelper(P, mid+1, last)\r\n\r\n  q \u2190 point of Sr with largest y-coordinate\r\n  return Sr \u222a UndominatedPoints(Sl, q)\r\n<\/pre>\n<\/li>\n
    3. Let H(n)<\/em> denote the running time of MaximalPointsHelper<\/tt> when it is called with a portion of P<\/em> that contains n<\/em> elements. Finding the point of Sr<\/tt> with largest y-coordinate and the call to UndominatedPoints<\/tt> takes O(n)<\/em> time, and so H(n)<\/em> satisfies the recurrence: H(n) = H(\u2308 n\/2\u2309) + H(\u230an\/2\u230b) + \u0398(n)<\/em> if n \u2265 2<\/em> with H(1) \u2208 \u0398(1)<\/em>. By case 2 of the Master theorem, H(n) \u2208 \u0398(n log n)<\/em>. The sorting step of algorithm MaximalPoints<\/tt> can also be done in \u0398(n log n)<\/em> time, using MergeSort<\/tt>, and so algorithm MaximalPoints<\/tt> runs in \u0398(n log n)<\/em> time.<\/li>\n<\/ol>\n<\/li>\n
    4. We use a recursion tree. We have drawn the first three levels of the tree. The blue text denotes the work done at each node (not all of these are written for the nodes on the third level, as that much text would have been very hard to read). The red text is the sum of the work at each level of the tree.
      \n<\/p>\n
      The root does 2n2<\/sup><\/em> work. The sum of the work on level 2<\/em> is 2(4n\/5)2<\/sup> + 2(2n\/5)2<\/sup> + 2(n\/5)2<\/sup> = 2n2<\/sup><\/em>. The sum of the work on level 3<\/em> is similarly 2n2<\/sup><\/em>.<\/p>\n
      The first leaf of the tree occurs at level log5<\/sub> n<\/em>. Because the first log5<\/sub>n<\/em> levels of the tree all do 2n2<\/sup><\/em> work, we thus get a lower bound of 2n2<\/sup>log5<\/sub>n<\/em> on T(n)<\/em>. The last leaf of the tree is at level log5\/4<\/sub>n<\/em>, and hence T(n) \u2264 2n2<\/sup>log5\/4<\/sub> n<\/em>. Since log5\/4<\/sub>n = log5<\/sub>n \/ log5<\/sub> (5\/4)<\/em> , this means that T(n) \u2208 \u0398(n2<\/sup>log n)<\/em>.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
      Algorithm UndominatedPoints(P, q) S \u2190 { } for each point p of P do if q.x < p.x or q.y < p.y then add p to S return S Algorithm MaximalPoints(P) sort P by increasing x-coordinate return MaximalPointsHelper(P, 0, length[P]-1) Algorithm MaximalPointsHelper(P, first, last) if first = last then return { P[first] } mid \u2190 … <\/p>\n
      Continue reading “Tutorial #8 solutions”<\/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-2506","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2506","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=2506"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2506\/revisions"}],"predecessor-version":[{"id":2507,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2506\/revisions\/2507"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/media?parent=2506"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}