2. You are spending your summer working at wonderful Funtime Resorts and Money S

ID: 3887499 • Letter: 2

Question

2. You are spending your summer working at wonderful Funtime Resorts and Money Sink, s with hours of entertaining rides, games, and gical place that provides your guest a ma excuses to spend their hard earned cash. Unfortunately, the park rules require all guests to exchange their normal currency for Funtime FunDollars before making any purchases. Funtime FunDollars come in only three denominations: 1FD bills, 4FD bills, and 6FD bills. As an employee of Funtime, you will need to make change (in FunDollars) for guests. (a) Consider the following greedy algorithm for making change for k FunDollars. Hand over the largest bill less than or equal to k, and then recursively make change for the amount that remains. Give an example where this strategy forces you to hand over more bills than the minimum possible. (b) Design a recursive algorithm that computes, given a value k, the minimum number of bills needed to make change for k FunDollars. You do not need to worry about making your algorithm efficient, but it should be correct. You should express the running time of your algorithm as a recurrence in k, but you do not have to solve the (c) Design and analyze an efficient algorithm that computes, given a value k, the minimunm number of bills needed to make change for k FunDollars. Your analysis should give the asymptotic running time of your algorithm in terms of k. This algorithm should be fast.

Explanation / Answer

a. Example can be an 8FD bill

From the given algorithm in part (a) ,the answer would be 3(6+1+1) but the correct answer is 2(4+4).So the greedy solution fails here.

Following is a simple recursive implementation of the problem. The implementation simply follows the recursive structure

Below is recursive solution based on above recursive formula.

C++

// A Naive recursive C++ program to find minimum of coins

// to make a given change V

#include<bits/stdc++.h>

using namespace std;

// m is size of coins array (number of different coins)

int minCoins(int coins[], int m, int V)

{

// base case

if (V == 0) return 0;

// Initialize result

int res = INT_MAX;

// Try every coin that has smaller value than V

for (int i=0; i<m; i++)

{

if (coins[i] <= V)

{

int sub_res = minCoins(coins, m, V-coins[i]);

// Check for INT_MAX to avoid overflow and see if

// result can minimized

if (sub_res != INT_MAX && sub_res + 1 < res)

res = sub_res + 1;

}

return res;

}

The time complexity of above solution is exponential. If we draw the complete recursion tree, we can observer that many subproblems are solved again and again