{"id":318,"date":"2015-02-20T16:54:55","date_gmt":"2015-02-20T23:54:55","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=318"},"modified":"2015-02-20T16:54:55","modified_gmt":"2015-02-20T23:54:55","slug":"tutorial-5-problems","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/02\/20\/tutorial-5-problems\/","title":{"rendered":"Tutorial #5 Problems"},"content":{"rendered":"<ol>\n<li>Give a recurrence relation for the running time of the following algorithm as a function of <i>n = last &#8211; first + 1<\/i>. To simplify your answer, do not specify the floors and ceilings in your recurrence.\n<pre>Algorithm TurtleSort(A, first, last)\n\nif (last - first \u2264 2) then\n    if (last - first \u2264 1) then\n        if (A[first] &gt; A[first+1]) then\n            swap (A[first], A[first+1])\n        endif\n\n        if (last - first = 2) then\n            if (A[last-1] &gt; A[last]) then\n                swap (A[last-1], A[last])\n            endif\n            if (A[first] &gt; A[first+1]) then\n                swap (A[first], A[first+1])\n            endif\n        endif\n    endif\n    return\nendif\n\nq1 \u2190 floor of (3*first +   last)\/4\nq2 \u2190 floor of (  first +   last)\/2\nq3 \u2190 floor of (  first + 3*last)\/4\n\nturtleSort(A, first, q2)\nturtleSort(A, q1, q3)\nturtleSort(A, q2, last)\nturtleSort(A, q1, q3)\nturtleSort(A, first, q2)\nturtleSort(A, q1, q3)\n<\/pre>\n<\/li>\n<li>Give a recurrence relation for the running time of the following algorithm as a function of <i>n = last &#8211; first + 1<\/i>. Note that your recurrence relation may have a summation in it.\n<pre>Algorithm MCM(A, first, last)\n\/\/\n\/\/ A is an array of objects, rows[X] and columns[X] are  \n\/\/ properties of object X whose value is an integer.\n\/\/\nif (first = last) then\n\treturn 0\nendif\n\nmin := +\u221e\nfor i := first to last - 1\n\tprod := rows[A[first]] * columns[A[i]] * \n                columns[A[last]];\n\tx := MCM(A, first, i) + MCM(A, i+1, last) + prod;\n\n\tif (x &lt; min ) then\n\t    min = x\n\tendif\nreturn min\n<\/pre>\n<\/li>\n<li>Using the <i>guess-and-test<\/i> method, prove that the function <i>T(n)<\/i> defined by the recurrence relation<br \/>\n<img decoding=\"async\" src=\"http:\/\/www.ugrad.cs.ubc.ca\/~cs320\/2014W1\/tutorials\/guessandtest.png\" alt=\"\" \/><br \/>\nis in <i>O(4<sup>n<\/sup>)<\/i>. (Hint: start by proving this bound for the same recurrence without the &#8220;<span style=\"color: #0000ff\"><strong>+<\/strong><em>n<\/em><\/span>&#8221; part. Then, modify your proof to handle that part.)<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Give a recurrence relation for the running time of the following algorithm as a function of n = last &#8211; first + 1. To simplify your answer, do not specify the floors and ceilings in your recurrence. Algorithm TurtleSort(A, first, last) if (last &#8211; first \u2264 2) then if (last &#8211; first \u2264 1) then [&hellip;]<\/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-318","post","type-post","status-publish","format-standard","hentry","category-tutorials"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/318","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=318"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/318\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=318"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=318"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=318"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}