HW5

Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)

(1) Please show ALL of your work (Step by Step).

(2) Provide as many details as possible for the designed algorithms (exact pseudocode) from now on. 

******************************************** Written ********************************************

1. [Written 10pt] Write pseudocode of the greedy algorithm for the change-making problem, with an amount n and coin denominations d1 > d2 > . . . > dm as its input. What is the time efficiency class of your algorithm?

2. [Written 10pt] Design a greedy algorithm for the assignment problem: There are n people who need to be assigned to execute n jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i,j =1,...,n. The problem is to assign people to jobs to minimize the total cost of the assignment. 

Does your greedy algorithm always yield an optimal solution? If it doesn't, provide a counterexample.

3. [Written 10pt] There are n people, each in possession of a different rumor. They want to share all the rumors with each other by sending electronic messages. Assume that a sender includes all the rumors he or she knows at the time the message is sent and that a message may only have one addressee. Design a greedy algorithm that always yields the minimum number of messages they need to send to guarantee that every one of them gets all the rumors.

4. [Written 10pt] Apply Prim’s algorithm to the following graphs (below). Include in the priority queue all the vertices not already in the tree (similar to the one we did in class or in the book).

5. [Written 10pt] Let T be a minimum spanning tree of graph G obtained by Prim’s algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges, with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T? If you answer yes, explain how; if you answer no, explain why not.

6. [Written 10pt] Apply Kruskal’s algorithm to find a minimum spanning tree of the following graphs (see below).

7. [Written 8pt] Indicate and show whether the following statements are true or false: 

a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph. 

b. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph. 

c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree. 

d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree.

8. [Written 10pt] What changes, if any, need to be made in algorithm Kruskal to make it find a minimum spanning forest for an arbitrary graph? (A minimum spanning forest is a forest whose trees are minimum spanning trees of the graph’s connected components.)

9. [Written 10pt] Explain what adjustments if any need to be made in Dijkstra’s algorithm and/or in an underlying graph to find a shortest path between two given vertices of a weighted graph or digraph. (This variation is called the single-pair shortest-path problem.)

10. [Written 10pt] Solve the following instance of the single-source shortest-paths problem with vertex a as the source (below). 

11. [Written 10pt] Give a counterexample that shows that Dijkstra’s algorithm may not work for a weighted connected graph with negative weights.

******************************************** Coding ********************************************

1. [Coding 10pt] Design an algorithm for finding a maximum spanning tree—a spanning tree with the largest possible edge weight—of a weighted connected graph. You function should take an n × n matrix (representing the adjacency matrix of a graph) as input and return the value of the maximum spanning the tree of the graph defined by the n × n matrix. Make sure to test your algorithm completely (include your test cases). 

2. [Coding 10pt] Design a function that should take an n × n vector (representing the adjacency matrix of a graph) and a value i between 0 and n − 1 as input and return the n-length vector representing the length of the shortest path from the ith node in the graph to every other node in the graph. You may assume the shortest path from a node to itself has length 0.