Lab 3: Currency Denominations and Weighted Graphs

Problem 1: Currency Denominations

(Q1) Given currency denominations: 1c, 5c, 10c, 25c, $1, devise a method to pay the amount to the customer using the fewest numbers of coins. The input is the total amount and the output should be the number of coins for each denomination.
Amount:  34 cents

Output:   1 coin of 25 cents

                 1 coin of 5 cents

                  4 coins of 1 cent

For further instructions and the starter code, download the file LabThree.java

 

(Q2) Write a program that reads, from an input file, a description of a weighted graph with integer weights, in the input format shown below. Then the program should write, on the standard output (Screen):

1. the original graph G;

2. the computed minimal spanning tree T of G;

3. the total weight of T.

To show a graph, show the number of vertices, the number of edges, and a list of all the edges, with their weights. Starting vertex for Prim’s algorithm is also given.

Make it clear just what each part of the output is. Don't make a reader guess what he or she is looking at. The output of your program might look like this. You should implement Kruskal and Prim’s algorithm to find the MST for the input graph. Resultant MST might be different for the two algorithms, output two different MSTs for each algorithm.

For further instructions and the starter code, download the file LabThree.java.

Input graph for Q2 will be read from a file "input_Q2.txt". There can be more than one input graphs. For a set of n vertices, set {1,2,3,...,n} will be used as the set of vertices.

First row of the input graph has 2 positive integers separated by a space, representing the number of vertices and the number of edges, respectively. Second row of the input graph has one integer value indicating the starting vertex for Prim’s algorithm. Every subsequent row contains 3 positive integers separated by a space. Among  these 3 values, the first two values are the end-points of an edge in the graph. The third value is the weight of the edge in the graph