CMSC 28100 / MATH 28100
Homeworks

Homework 1 (35 pts)

Due in class on Wednesday, April 8.

Prove the correctness of Kruskal's algorithm done in class. (10 points)
Consider the following problem: Given a weighted graph G = (V,E), with non negative edge weights w_e(e∈E) and a given source vertex v₀. Give an algorithm to find the minimum weight (shortest) path from v₀ to all the other vertices of the graph. (10 points)

Hint: Think of a greedy approach where you visit particular vertices, keep on updating the weight of the path to all its neighbors according to the lowest cost path encountered till then and then jump to an appropriate neighbor to repeat the whole process.
What is the time complexity of the algorithm in terms of |V| and |E|? Give a correctness proof of your algorithm. (15 points)

Hint: For the latter, you might want to consider an invariant: there are three sets of vertices in the graph in terms of reachability at any time. What are they? Try to prove that whenever we add the vertices to a particular one of those sets, the path to it is the shortest path from the source.
(For fun) Do you see why it is necessary to have non negative edge weights for this algorithm?