ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 3
1. Consider a union-find implementation that uses the same basic strategy as weighted quickunion but keeps track of tree height and always links the shorter tree to the taller one. Prove a logarithmic upper bound on the height of trees for N sites for this scheme.
2. Give a proof of correctness for Algorithm 4.10, for computing shortest paths in edgeweighted Directed Acyclie Graphs (DAGS). Use proof by contradiction technique.
3. If the PQ is implemented as an unsorted sequence, show that Dijkstra’s algorithm runs in O(n2) time. For what type of graphs is this implementation preferred?
4. If at the end of the execution of Bellman-Ford algorithm, there is an edge (u,z) that can be potentially relaxed (that is, D[u] + w(u,z) < D[z], then show that the input digraph G contains a negative-weight cycle.
