Greedy + Divide & Conquer

Greedy + Divide & Conquer

1. Greedy + Divide & Conquer Coin-change Problem Vaishnav S Chandran CSE23009

2. Greedy Approach The greedy method is a problem-solving strategy where the best possible solution at the current instance is chosen. This results in efficient computations but may not always provide the most optimal solution.

3. Pseudocode GreedyCoinChangeFor29Cents() Coins = [50, 25, 10, 5, 1] // Already sorted in descending order Amount = 29 Count = 0 for coin in Coins: while Amount >= coin: Amount -= coin Count += 1 return Count

4. Output For the given coin types {1, 5, 10, 25, 50} and a target amount of 29 cents, the Greedy algorithm works as follows: Take the largest coin less than or equal to 29 (25-cent coin), Remaining = 4 Take the largest coin less than or equal to 4 (4 x 1-cent coins), Remaining = 0 So, you would need one 25-cent coin and four 1-cent coins, totaling 5 coins. Time Complexity: O ( n log n ) (due to sorting) Space Complexity: O ( m ) where m is the number of coins used.

5. Divide-and-Conquer General Idea: Solve a larger problem by: dividing it into small problem(s) solving the smaller problem(s) use solution(s) to smaller problem(s) to solve original problem

6. Pseudocode FOR each coin in Coins: NumCoins = 1 + DivideAndConquerCoinChangeFor29Cents(Coins, Amount - coin) IF NumCoins < MinCoins THEN MinCoins = NumCoins END IF END FOR RETURN MinCoins END FUNCTION FUNCTION DivideAndConquerCoinChangeFor29Cents(Coins[], Amount) IF Amount == 0 THEN RETURN 0 END IF IF Amount < 0 THEN RETURN Infinity END IF MinCoins = Infinity

7. Output The Divide and Conquer algorithm will explore all possible combinations. For the US coin types {1, 5, 10, 25, 50} and an amount of 29, the algorithm will find: Minimum number of coins to make change for 28, 24, 19, 4, and -21 (not valid) Combine these sub-solutions to find the minimum number of coins needed for 29 The algorithm will determine that the minimum number of coins for 29 cents is also 5 coins: one 25-cent coin and four 1-cent coins. Time Complexity: O ( Amount × n ) Space Complexity: O ( Amount )

8. Time and Space Complexity Greedy: Time Complexity: O ( n ) Space Complexity: O (1) Divide and Conquer: Time Complexity: O ( Amount × n ) Space Complexity: O ( Amount ) Both approaches would return 5 as the minimum number of coins needed to make 29 cents but with different computational costs.

9. Comparison: Efficiency : In this example, the Greedy algorithm is faster but both algorithms provide the optimal solution. This is because the US coin denominations are such that the Greedy algorithm works perfectly. Output : Both algorithms would return the minimum number of coins as 5: one 25-cent coin and four 1-cent coins. Complexity : Greedy has a better time complexity due to its inherent design. However, it is crucial to note that Greedy would not always give the optimal solution for different sets of coin denominations. The Divide and Conquer approach is guaranteed to provide an optimal solution but is computationally more expensive.

10. Thank You