- 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, a blast from the past).
- 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.
- 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 = {x0, x1, … xn-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 minimum 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).
Tutorial #3 Problems
Leave a reply