java programming part 1 : Suppose you are a manager in the IT department for the
ID: 3839028 • Letter: J
Question
java programming
part 1 :
Suppose you are a manager in the IT department for the government of a corrupt dictator, who has a collection of computers that need to be connected together to create a communication network for his spies. You are given a weighted graph, G, such that each vertex in G is one of these computers and each edge in G is a pair of computers that could be connected with a communication line. It is your job to decide how to connect the computers. Suppose now that the CIA has approached you and is willing to pay you various amounts of money for you to choose some of these edges to belong to this network (presumably so that they can spy on the dictator). Thus, for you, the weight of each edge in G is the amount of money, in U.S. dollars, that the CIA will pay you for using that edge in the communication network. Implement an efficient algorithm, therefore, for finding a maximum spanning tree in G, which would maximize the money you can get from the CIA for connecting the dictator’s computers in a spanning tree. What is the running time of your algorithm?
Your program will take as input a file with edge information. Each line in the file contains from, to and weight. You may assume the vertices are numbered from 0 to N. The weights are unique and non-negative. It will construct the Graph and print the edges in the maximum spanning tree. Write java program that reads in from text file and creates maximum spanning tree graph.
part 2:
Suppose that the coins of the fictional country of Combinatoria come in the de- nominations, d1, d2, . . . , dk, where d1 = 1 and the other di values form a set of distinct integers greater than 1. Given an integer, n > 0, the problem of making change is to find the fewest number of Combinatorian coins whose values sum to n.
(a) Give an instance of the making-change problem for which it is suboptimal to use the standard greedy algorithm, which repeatedly chooses a highest-valued coin whose value is at most n until the sum of chosen coins equals n. (writeup only)
(b) Implement the algorithm for the coin changing problem. Take as input a file with a set of denominations. Interactively ask the user for the amount he wants to make change for and print the number of coins and the actual change.
A discussion of this well known dynamic programming problem can be found at http://www.ccs.neu.edu/home/jaa/CS7800.12F/Information/Handouts/dyn_prog.pdf (Links to an external site.)Links to an external site. including the pseudocode for the optimal solution.
Explanation / Answer
Hi, Please find my solution for Part2.
Please repost other in separate post.
Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins,
what is the minimum number of coins to make the change?
Examples:
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents
Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents
The minimum number of coins for a value V can be computed using below recursive formula.
If V == 0, then 0 coins required.
If V > 0
minCoin(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])}
where i varies from 0 to m-1
and coin[i] <= V
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. For example, when we start from V = 11, we can reach 6 by subtracting one 5 times and by subtracting 5 one times. So the subproblem for 6 is called twice.
Since same suproblems are called again, this problem has Overlapping Subprolems property. So the min coins problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner. Below is Dynamic Programming based solution.
Time complexity of the above solution is O(mV).
public class MinimumCoins {
// m is size of coins array (number of different coins)
static int minCoins(int coins[], int m, int V)
{
// table[i] will be storing the minimum number of coins
// required for i value. So table[V] will have result
int table[] = new int[V+1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i=1; i<=V; i++)
table[i] = Integer.MAX_VALUE;
// Compute minimum coins required for all
// values from 1 to V
for (int i=1; i<=V; i++)
{
// Go through all coins smaller than i
for (int j=0; j<m; j++)
if (coins[j] <= i)
{
int sub_res = table[i-coins[j]];
if (sub_res != Integer.MAX_VALUE && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
return table[V];
}
public static void main(String[] args) {
int coins[] = {9, 6, 5, 1};
int m = 4;
int V = 11;
System.out.println("Minimum coins required is "+minCoins(coins, m, V));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.