CSC 226
ALGORITHMS AND DATA STRUCTURES II
ASSIGNMENT 3
1. Suppose all edge weights in a graph are integers in the range from 1 to |V | where V is the
set of vertices. How fast can you make Kruskal’s algorithm run? Explain.
2. Given an MST for an edge-weighted graph G, suppose that an edge in G that does not
disconnect G is deleted. Design an algorithm using which we could find the minimum
spanning tree for the modified graph easily without constructing the new tree from scratch
again. What is its running time?
3. Show how to solve the single source shortest path problem of the graph in the lecture
slides on Dijkstra’s algorithm, slide 11 using Dijkstra’s algorithm, when the source node
is g. Give the initial values of D(v) for each node v. Each time a node is pulled into the
cloud, give the D values which have changed as a result.
4. Show how to solve the single source shortest path problem of the graph in the lecture
slides on Bellman-Ford’s algorithm, slide 8 using the Belllman Ford algorithm, when the
source node is b. Give the sequence of D values for all the nodes initially and then just
give changes to D values which occurs, by giving the node affected and its new D value,
in order of which they occur. In each round, consider the edges in lexicographic order.
5. Design an algorithm for the single source shortest path problem (SSSP) on directed acyclic
graphs (DAGs) in O(m + n) time.
1
