{"id":117,"date":"2015-01-16T19:00:17","date_gmt":"2015-01-17T02:00:17","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=117"},"modified":"2015-01-16T19:00:17","modified_gmt":"2015-01-17T02:00:17","slug":"tutorial-2-problems","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/01\/16\/tutorial-2-problems\/","title":{"rendered":"Tutorial #2 Problems"},"content":{"rendered":"
    \n
  1. Rank the following functions by order of growth. That is, order them so that f1<\/sub> \u2208 O(f2<\/sub>), f2<\/sub> \u2208 O(f3<\/sub>), etc. Make sure to indicate whether or not fi<\/sub> \u2208 \u0398(fi+1<\/sub>). For instance you could use the notation O(n) \u2282 O(n^2) = O(2n^2) \u2282 O(n^4)...<\/tt>
    \n\n\n\n\n\n\n
    n3<\/sup> – n \u221a\u00a0n\u00a0<\/span>
    \n<\/span><\/td>\n    		n!<\/td>\nlog (log n)<\/td>\n1.01n<\/sup><\/td>\n<\/tr>\n
    \u221a\u00a0n log n\u00a0<\/span>
    \n<\/span><\/td>\n    		17<\/td>\n4913n289<\/sup><\/td>\n32n-17<\/sup><\/td>\n<\/tr>\n
    1.011.01n<\/sup><\/sup><\/td>\n\u221a\u00a0n\u00a0<\/span>
    \n<\/span><\/td>\n    		3n<\/sup><\/td>\nnn<\/sup><\/td>\n<\/tr>\n
    n18\/17<\/sup><\/td>\nn log17<\/sup> n<\/td>\n32n<\/sup><\/td>\nn3<\/sup> + log n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/li>\n
  2. Prove that for each fixed<\/b> value of k<\/i> > 0, 1k<\/sup> +\u00a02k<\/sup> + … + (t-1)k<\/sup> + tk<\/sup> \u2208\u00a0\u0398(tk+1<\/sup>)<\/i>. Hint: do not use induction. Instead, treat k\u00a0<\/i>as a constant, and do O<\/i> and \u03a9<\/i> separately. (Remember that for\u00a0\u03a9<\/i> bounds, it is legal to drop positive terms and reduce the size of positive terms, since you can guarantee that the resulting function is still a lower bound on the original.)<\/li>\n
  3. Analyze the running time of the following algorithm as a function of n,\u00a0assuming that each arithmetic operation takes constant time. Use O, \u03a9 or\u00a0\u0398 notation as appropriate to express your result as simply and as precisely as\u00a0possible. Give an informal argument (not necessarily a full proof) to support your\u00a0answer. (It may help to think about the “measure of progress” approach the book used to analyze the while loop in the Gale-Shapley Algorithm.)\n
    Algorithm Strange(n)\n    sum \u2190 0\n    while (n > 3) do\n        sum \u2190 sum + n\n        if (n is even) then\n            n \u2190 n \/ 2\n        else\n            n \u2190 n + 3\n        endif\n    return sum\n<\/pre>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    Rank the following functions by order of growth. That is, order them so that f1 \u2208 O(f2), f2 \u2208 O(f3), etc. Make sure to indicate whether or not fi \u2208 \u0398(fi+1). For instance you could use the notation O(n) \u2282 O(n^2) = O(2n^2) \u2282 O(n^4)… n3 – n \u221a\u00a0n\u00a0 n! log (log n) 1.01n \u221a\u00a0n […]<\/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-117","post","type-post","status-publish","format-standard","hentry","category-tutorials"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/117","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=117"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/117\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}