Please write the whole in java code only for coinchange1& coinchange2 . If possible attempt additional activities too!

Lab: Coin Change The Problem Calculating change is something that we have been trained to do from a young age. For example, without thinking about it, we all know how many quarters, dimes, nickels and pennies we should receive if the change from our purchase is 47 cents. In this lab, you will write a program to convert a given amount of money (in cents) into change. Notice, however, that there are many ways to calculate change. That is, if our change is 47 cents, we could use 47 pennies. Or we could use 3 dimes and 17 pennies. Or we could use 4 dimes, a nickel, and 2 pennies. You get the idea. What we would really like to do is use a minimal number of coins. For 47 cents, one way to use a minimal number of coins is 1 quarter, 2 dimes, and 2 pennies. For this lab, you will implement a greedy solution for the problem of calculating change. What is a greedy solution? It is quite simple. Assume you want to convert an arbitrary number of cents into coins of the following denominations: dollar, half-dollar, quarter, dime, nickel, and penny. Use as many dollar coins as possible; then, on what's left over, use as many half-dollar coins as possible; then again as many quarters as possible; then as many dimes as possible; then as many nickels as possible; finally the remainder is in pennies. Method 1. Edit CoinChangel.java (including updating comments appropriately) to ask the user for an amount (number of cents) to make change for and then use the greedy solution to compute and output the numbers of coins of each kind required to make that amount of change. As mentioned before, you should use coins of the following denominations: dollar, half-dollar, quarter, dime, nickel, and penny. Hint: if you have any loops in your code, try again. 2. Copy Coinchangel.java to create coinchange2.java (right-click on Coinchangel.java to get the contextual pop-up menu and choose Copy, then right-click on (default package) and choose Paste, providing the new name Coinchange2). Modify the program so that it solves the same problem, with the same greedy solution, but uses arrays (one for the coin denominations and one for the coin counts) and one loop with a simple body to replace the longer straight-line code in CoinChangel.java. Note that this change also generalizes the solution so it can be easily modified, by changing a single line of code, to work with other coin denominations. 3. Can you convince yourself and your partner that the greedy solution is optimal, i.e., it solves the problem with a minimum number of coins? Additional Activities 1. Regarding the last question above, consider what happens if the coin denominations available are 100, 60, and 1. What is the greedy solution for 120 cents ? 2. Copy CoinChange2.java to create Coinchange3.java. Introduce a private static method called coinCountsToMakeChange that has two formal parameters: the number of cents for which change is needed, and the array of coin denominations to be used to make change; and that returns an array of coin counts for the respective denominations. As a model of approximately what this might look like, see myMethod in the sample Java code ProgramWithI0AndStaticMethod.java in the Project Template. 3. Copy Coinchange3.java to create coinchange4.java. Modify the program so that it uses a different (non-greedy) solution that gives an optimal answer for any combination of coin denominations. Note that you should not be too disturbed if you cannot find an algorithm for this problem that is "fast" for all possible denominations of coins. On the other hand, you should be very pleased if you can -- because it would solve an important open theoretical problem in computer science and mathematics for which a solution would earn you a $1M prize and unfathomable fame. (Well, you'd be famous among theoreticians and would certainly be featured in an article in the New York Times. It is beyond the scope of this course to explain why the Clay Mathematics Institute rather than a vending-machine maker should care this much about a seemingly simple problem like making change.) Lab: Coin Change The Problem Calculating change is something that we have been trained to do from a young age. For example, without thinking about it, we all know how many quarters, dimes, nickels and pennies we should receive if the change from our purchase is 47 cents. In this lab, you will write a program to convert a given amount of money (in cents) into change. Notice, however, that there are many ways to calculate change. That is, if our change is 47 cents, we could use 47 pennies. Or we could use 3 dimes and 17 pennies. Or we could use 4 dimes, a nickel, and 2 pennies. You get the idea. What we would really like to do is use a minimal number of coins. For 47 cents, one way to use a minimal number of coins is 1 quarter, 2 dimes, and 2 pennies. For this lab, you will implement a greedy solution for the problem of calculating change. What is a greedy solution? It is quite simple. Assume you want to convert an arbitrary number of cents into coins of the following denominations: dollar, half-dollar, quarter, dime, nickel, and penny. Use as many dollar coins as possible; then, on what's left over, use as many half-dollar coins as possible; then again as many quarters as possible; then as many dimes as possible; then as many nickels as possible; finally the remainder is in pennies. Method 1. Edit CoinChangel.java (including updating comments appropriately) to ask the user for an amount (number of cents) to make change for and then use the greedy solution to compute and output the numbers of coins of each kind required to make that amount of change. As mentioned before, you should use coins of the following denominations: dollar, half-dollar, quarter, dime, nickel, and penny. Hint: if you have any loops in your code, try again. 2. Copy Coinchangel.java to create coinchange2.java (right-click on Coinchangel.java to get the contextual pop-up menu and choose Copy, then right-click on (default package) and choose Paste, providing the new name Coinchange2). Modify the program so that it solves the same problem, with the same greedy solution, but uses arrays (one for the coin denominations and one for the coin counts) and one loop with a simple body to replace the longer straight-line code in CoinChangel.java. Note that this change also generalizes the solution so it can be easily modified, by changing a single line of code, to work with other coin denominations. 3. Can you convince yourself and your partner that the greedy solution is optimal, i.e., it solves the problem with a minimum number of coins? Additional Activities 1. Regarding the last question above, consider what happens if the coin denominations available are 100, 60, and 1. What is the greedy solution for 120 cents ? 2. Copy CoinChange2.java to create Coinchange3.java. Introduce a private static method called coinCountsToMakeChange that has two formal parameters: the number of cents for which change is needed, and the array of coin denominations to be used to make change; and that returns an array of coin counts for the respective denominations. As a model of approximately what this might look like, see myMethod in the sample Java code ProgramWithI0AndStaticMethod.java in the Project Template. 3. Copy Coinchange3.java to create coinchange4.java. Modify the program so that it uses a different (non-greedy) solution that gives an optimal answer for any combination of coin denominations. Note that you should not be too disturbed if you cannot find an algorithm for this problem that is "fast" for all possible denominations of coins. On the other hand, you should be very pleased if you can -- because it would solve an important open theoretical problem in computer science and mathematics for which a solution would earn you a $1M prize and unfathomable fame. (Well, you'd be famous among theoreticians and would certainly be featured in an article in the New York Times. It is beyond the scope of this course to explain why the Clay Mathematics Institute rather than a vending-machine maker should care this much about a seemingly simple problem like making change.)