# 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 we(e∈E) and a given source vertex v0. Give an algorithm to find the minimum weight (shortest) path from v0 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

## Homework 3

Due in class on Wednesday, April 22.

## Homework 4

Due in class on Wednesday, April 29.

## Homework 5

Due in class on Wednesday, May 13.

## Homework 6

Due in class on Wednesday, May 20.
Last revised: April 17, 2009.