{"id":151,"date":"2015-01-12T08:26:09","date_gmt":"2015-01-12T15:26:09","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=151"},"modified":"2015-01-12T08:26:09","modified_gmt":"2015-01-12T15:26:09","slug":"slides-4","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/01\/12\/slides-4\/","title":{"rendered":"Slides #4"},"content":{"rendered":"<ul>\n<li>Asymptotic analysis and orders of growth <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/files\/2015\/01\/2015-01-12-notes.pdf\">problems handout<\/a>.<\/li>\n<li>Some notes on\u00a0<a href=\"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/files\/2015\/01\/2015-01-12-little-o-omega-notes.pdf\">Little-\u03bf and Little-\u03c9<\/a>.<\/li>\n<\/ul>\n<p>Our reading question on this set was essentially:<\/p>\n<p style=\"padding-left: 30px\">Consider the following problem: Given a list of n integers, determine whether any subset of ____ of the integers\u00a0sum to 42.<\/p>\n<p style=\"padding-left: 30px\">Now, with a brute force solution, does this take polynomial or exponential time?<\/p>\n<p>The blank in that was filled with &#8220;three&#8221; for one section and with &#8220;any size&#8221; for the other section. For &#8220;three&#8221;, the answer is polynomial time because we can construct a triply nested loop to produce all sets of size three and check each one in constant time. (For &#8220;four&#8221;, it would be a quadruply nested loop.) For &#8220;any size&#8221;, the answer is exponential because there are 2<sup>n<\/sup> subsets of n elements.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Asymptotic analysis and orders of growth problems handout. Some notes on\u00a0Little-\u03bf and Little-\u03c9. Our reading question on this set was essentially: Consider the following problem: Given a list of n integers, determine whether any subset of ____ of the integers\u00a0sum to 42. Now, with a brute force solution, does this take polynomial or exponential time? [&hellip;]<\/p>\n","protected":false},"author":7560,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[318531],"tags":[],"class_list":["post-151","post","type-post","status-publish","format-standard","hentry","category-handouts"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/151","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=151"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/151\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}