{"id":349,"date":"2015-02-27T17:30:52","date_gmt":"2015-02-28T00:30:52","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=349"},"modified":"2015-02-27T17:30:52","modified_gmt":"2015-02-28T00:30:52","slug":"tutorial-6","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/02\/27\/tutorial-6\/","title":{"rendered":"Tutorial #6 Problems"},"content":{"rendered":"
    \n
  1. Prove upper and lower bounds on the function T(n)<\/i> defined by T(n) = 6T(\u230an\/2\u230b) + 16T(\u230an\/4\u230b) + 2n3<\/sup><\/i> when n \u2265 4<\/i>, with T(1) = T(2) = T(3) = 1<\/i>.<\/li>\n
  2. Consider the problem of taking a sorted<\/b> array A<\/i> containing distinct (and not necessarily positive) integers, and determining whether or not there is a position i<\/i> such that A[i] = i<\/i>.\n
      \n
    1. Describe a divide-and-conquer algorithm to solve this problem. Your algorithm should return such a position if it exists, or false<\/tt> otherwise. If A[i] = i<\/i> for several different integers i<\/i>, then you may return any one of them.<\/li>\n
    2. Analyze the running time of your algorithm as a function of the number of elements of A<\/i>.<\/li>\n<\/ol>\n<\/li>\n
    3. 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
        \n
      • How much the treasure is worth.<\/li>\n
      • How easy it would be for Yprantou (the royal thief) to acquire<\/em> this treasure.<\/li>\n<\/ul>\n

        Each treasure can thus be represented by a point in the plane: the x<\/em> coordinate represents how much the treasure is worth, and the y<\/em>coordinate is the difficulty of stealing that treasure (where a higher y<\/em> coordinate corresponds to a treasure that is easier to steal). Given two such points, we will say that a point q = (q.x, q.y)<\/em> dominates<\/strong> the point p = (p.x, p.y)<\/em> if q.x \u2265 p.x<\/em> and q.y \u2265 p.y<\/em>. That is, q<\/em> lies to the right of and above p<\/em>, as illustrated in picture on the left.Clearly, a point p<\/em> that is dominated by a point q<\/em> is of no interest, since q<\/em> is both worth more and easier to steal than p<\/em>. Hence, to help you reach a decision, you only need to worry about locations that correspond to maximal<\/strong> points: those that no other point dominates. For instance, in the picture on the right, the points p3<\/sub><\/em>, p4<\/sub><\/em> are p6<\/sub><\/em> are maximal, as you can see from the fact that their upper-right quadrants are empty.<\/p>\n

        \"\"<\/p>\n

          \n
        1. Describe an algorithm that takes as input a set P<\/em> of points, and a point q<\/em>, and returns all points of P<\/em> that q<\/em> does not dominate.<\/li>\n
        2. Describe an efficient divide-and-conquer algorithm that takes as input a set P<\/em> of points, and returns the list of treasures that Yprantou might be asked to steal first (that is, all maximal points of P<\/em>). Hints<\/em>:\n
            \n
          • Try to\u00a0divide the problem into two subproblems so that points that are maximal in one of the subproblems are guaranteed to be maximal in P<\/em>.<\/li>\n
          • 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 to eliminate maximal points from the other subproblem that are not maximal in P<\/em>.<\/li>\n<\/ul>\n<\/li>\n
          • Analyze the worst-case running time of your algorithm from (b).<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

            Prove upper and lower bounds on the function T(n) defined by T(n) = 6T(\u230an\/2\u230b) + 16T(\u230an\/4\u230b) + 2n3 when n \u2265 4, with T(1) = T(2) = T(3) = 1. Consider the problem of taking a sorted array A containing distinct (and not necessarily positive) integers, and determining whether or not there is a position […]<\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3426],"tags":[],"class_list":["post-349","post","type-post","status-publish","format-standard","hentry","category-tutorials"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/349","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/users\/7560"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/comments?post=349"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/349\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=349"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=349"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=349"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}