Computer Science > QUESTIONS & ANSWERS > Georgia Institute Of Technology CS 8803 GA Exam 2 Solutions-ALL ANSWERS CORRECT (All)

Georgia Institute Of Technology CS 8803 GA Exam 2 Solutions-ALL ANSWERS CORRECT

Document Content and Description Below

CS 8803GA Exam 2 Solutions Problem 1: Short Answer (a) What is the running time of Dijkstras algorithm (with min-heap implementation) on a graph with n vertices and m edges? Solution. O((n + m) ... log n) (b) Dijkstra’s algorithm is guaranteed to work correctly if the graph is directed with edge lengths that are non-negative (so they can be positive or zero, but not negative): Solution. TRUE If there are negative length edges then dist(v) can decrease after v has been explored, but if the lengths are non-negative then this cannot occur and hence Dijkstra’s algorithm works correctly. (c) Consider a MST T for undirected G = (V; E). Now suppose for every edge e in G, we replace its edge weight w(e) by w(e) + 1, so we increase every edge weight by +1. The tree T is guaranteed to still be a minimum spanning tree for this new weighted graph: Solution. TRUE A spanning tree has exactly n − 1 edges, so increasing each edge weight by 1 increases the weight of all spanning trees by n−1. It will not change the relative weights of two spanning trees, so a MST in the original graph will still be a MST in the new one. (d) Consider a MST T for undirected G = (V; E). Now suppose for every edge e in G, we replace its edge weight w(e) by: w^(e) = (2 0 if w(e) if w w( (e e) ) > ≤ 100 100 The tree T is guaranteed to still be a minimum spanning tree for this new weighted graph: Solution. TRUE If an edge e was minimum across some cut (S; S) in the original weighting scheme then it is still minimum across this same cut in the new weighting scheme (if it has weight ≤ 100 then there may be additional edges of the same new weight but e is still minimum). 1Problem 2: MST For an undirected graph G = (V; E) with weights w(e) > 0 for each edge e 2 E, you are given a MST T. Unfortunately one of the edges e∗ = (u; z) which is in the MST T is deleted from the graph G (no other edges change). Give an algorithm to build a MST for the new graph. Your algorithm should start from T. Note: G is connected, and G − e∗ is also connected. Explain your algorithm in words and use the algorithms from class as black-box subroutines. Clearly state and explain the running time of your algorithm. To receive credit, your algorithm should be correct and faster in O() than building a MST from scratch (so dont use Prim’s or Kruskal’s, even part of Kruskal’s). Solution. Let u and v be the two endpoints of e∗. Look at T − e∗. Let Tu and Tv be the tw [Show More]

Last updated: 2 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: