#
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*_{0}. Give an algorithm to find the
minimum weight (shortest) path from *v*_{0} 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?

## Homework 2 (50 pts)

Due in class on Wednesday, April 15.
- Exercise 8.2.2 parts (b) and (c). (10 pts each)
- Exercise 8.2.3 part (a). (10 pts)
- Exercise 8.2.5 parts (b) and (c). (10 pts)
- For Fun: 8.2.4

Due in class on Wednesday, April 22.
Due in class on Wednesday, April 29.
Due in class on Wednesday, May 13.
Due in class on Wednesday, May 20.

Last revised: April 17, 2009.