Sample problems for tutorial #3

1. 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 consisting of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent).
   • Give an example showing that there are set of coin values (although obviously not those used in Canada) for which the greedy algorithm does not always return a solution using the least possible number of coins.
2. In the Exhibition Guarding Problem, we are given a line L that represents a long hallway in a show room. We are also given an unordered set X = { x₀, x₁, ... x_n-1 } of 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 d of his or her position, on both sides.

   • Design an algorithm for finding a placements of guards that uses the minium number of guards to guard all the objects with positions in X.
   • Analyze the running time of your algorithm as a function of n, the number of objects that need guarding.
   • Prove that your algorithm works (write as complete an argument as you can in the time available in the tutorial).