{"id":206,"date":"2015-01-23T17:00:31","date_gmt":"2015-01-24T00:00:31","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?p=206"},"modified":"2015-01-23T17:00:31","modified_gmt":"2015-01-24T00:00:31","slug":"tutorial-3-problems","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/2015\/01\/23\/tutorial-3-problems\/","title":{"rendered":"Tutorial #3 Problems"},"content":{"rendered":"<ol>\n<li>Consider the problem of making change for <em>n<\/em> cents, using the least number of coins. The input to this problem is the integer <em>n<\/em>, and the output is a sequence of coin values (where each value is allowed to appear multiple times) whose sum adds up to <em>n<\/em>.\n<ol>\n<li>Describe a greedy algorithm to make change consisting of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent, a blast from the past).<\/li>\n<li>Give an example showing that there are set of coin values (although obviously not quarters, dimes, nickels, and pennies) for which the greedy algorithm does not always return a solution using the least possible number of coins.<\/li>\n<\/ol>\n<\/li>\n<li>In the Exhibition Guarding Problem, we are given a line <em>L<\/em>\u00a0that represents a long hallway in a show room. We are also given an unordered set <em>X<\/em> = {<em>x<sub>0<\/sub><\/em>, <em>x<sub>1<\/sub><\/em>, &#8230; <em>x<sub>n-1<\/sub><\/em>}\u00a0of real numbers that represent the positions of precious objects or sculptures in this hallway. Suppose that a single guard can protect all the objects within distance at most <em>d<\/em> of his or her position, on both sides.\n<ol>\n<li>Design an algorithm for finding a placements of guards that uses the minimum number of guards to guard all the objects with positions in <em>X<\/em>.<\/li>\n<li>Analyze the running time of your algorithm as a function of <em>n<\/em>, the number of objects that need guarding.<\/li>\n<li>Prove that your algorithm works (write as complete an argument as you can in the time available in the tutorial).<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Consider the problem of making change for n cents, using the least number of coins. The input to this problem is the integer n, and the output is a sequence of coin values (where each value is allowed to appear multiple times) whose sum adds up to n. Describe a greedy algorithm to make change [&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-206","post","type-post","status-publish","format-standard","hentry","category-tutorials"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/206","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=206"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/posts\/206\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/media?parent=206"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/categories?post=206"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202014w2\/wp-json\/wp\/v2\/tags?post=206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}