Mathematics > QUESTIONS & ANSWERS > Georgia Institute Of Technology CS 8803-GA midterm2-solutions (All)

Georgia Institute Of Technology CS 8803-GA midterm2-solutions

Document Content and Description Below

Midterm 2 Solutions Problem 1. Provide the following information: Your name; Your SID number; Your section number (and/or your TA name); Name of the person on your left (if any); Name of the person... on your right (if any). Solutions The correct spelling of the TA’s names are Scott Aaronson, Shyam Lakshmin, Iordanis (Jordan) Kerenidis, Joseph (Joe) Polastre, Beini Zhou. We gave full credit as long as you could spell your own name. (And we were not too strict in checking that, either.) Common mistakes involved the spelling of Beini’s and Jordan’s last names. Problem 2. Consider a undirected graph G = (V; E) with nonnegative weights w(i; j) ‚ 0 on its edges (i; j) 2 E. Let s be a node in G. Assume you have computed the shortest paths from s, and minimum spanning tree of the graph. Suppose we change the weights on every edge by adding 1 to each of them. The new weights are w0(i; j) = w(i; j)+ 1 for every (i; j) 2 E. (a) Would the minimum spanning tree change due to the change in weights? Give an example where it changes or prove that it cannot change. (b) Would the shortest paths change due to the change in weights? Give an example where it changes or prove that it cannot change. Solutions The first question was, if T is a minimum spanning tree of a graph G, and if every edge weight of G is incremented by 1, is T still an MST of G? The answer is yes. The simplest proof is that, if G has n vertices, then any spanning tree of G has n ¡ 1 edges. Therefore incrementing each edge weight by 1 increases the cost of every spanning tree by a constant, n ¡ 1. So any spanning tree with minimal cost in the original graph also has minimal cost in the new graph. There are alternative proofs that amount to more complicated ways of saying the same thing. For example: assume by way of contradiction that T is not an MST of the new graph. Then there is some other spanning tree of G, call it Tb 6= T, with lower cost on the new graph. Given a cut (R; S) of G, T has exactly one edge e and Tb has exactly one edge eb crossing the cut. Suppose eb 6= e and eb has lower cost than e. Then by replacing e [Show More]

Last updated: 2 years ago

Preview 1 out of 7 pages

Buy Now

Instant download

We Accept: