In the interval partitioning problem we explored on Homework 5, the greedy choice that considers the intervals in decreasing order by end time (rather than increasing order by end time) does result in an optimal algorithm. The greedy algorithm proof technique based on the exchange argument basically iteratively transforms an "optimal" solution that is not the greedy one into the one the greedy algorithm would return. Dijkstra's algorithm computes the shortest cost path from every vertex in a graph to every other vertex in a graph. Dijkstra's algorithm will work, without modificati n, on a graph that has negative weight edges, as long as there are no negative weight cycles. For a dense graph (when m> ), the running time of Prim's algorithm (which is O(mlogn) ) is asymptotically faster than Kruskal's algorithm (which is O(mlogm) ). In a graph where each edge has a unique weight, there is only a single minimum spanning tree. In the Interval Scheduling Problem we discussed in class (where our goal is to schedule the maximum number of compatible jobs), the job with the earliest finishing time will be present in every optimal solution. If all edges in a graph have equal weight, then the shortest path between two nodes is the path with the least number of edges between those two nodes. Let T be the MST of a graph G, then the path from u to v in T is the shortest path from u to v in G. The first step of every greedy algorithm is to sort the input in some way using some metric