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
m
The correct spelling of the TA’s names are Scott Aaronson, Shyam Lakshmin, Iordanis (Jordan)
er as
Kerenidis, Joseph (Joe) Polastre, Beini Zhou.
co
eH w
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
o.
last names.
rs e
ou urc
Problem 2. Consider a undirected graph G = (V, E) with nonnegative weights w(i, j) ≥
0 on its edges (i, j) ∈ E. Let s be a node in G. Assume you have computed the shortest
o
paths from s, and minimum spanning tree of the graph. Suppose we change the weights on
aC s
every edge by adding 1 to each of them. The new weights are w0 (i, j) = w(i, j) + 1 for every
vi y re
(i, j) ∈ 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.
ed d
(b) Would the shortest paths change due to the change in weights? Give an example
ar stu
where it changes or prove that it cannot change.
Solutions
is
The first question was, if T is a minimum spanning tree of a graph G, and if every edge
Th
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,
sh
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 with
This study source was downloaded by 100000827039679 from CourseHero.com on 07-01-2021 10:22:31 GMT -05:00
https://www.coursehero.com/file/42774271/midterm2-solpdf/
, Handout MS2: Midterm 2 Solutions 2
eb, we obtain a new spanning tree for the original graph with lower cost than T , since the
ordering of edge weights is preserved when we add 1 to each edge weight. This contradicts
the assumption that T was an MST of the original graph.
Many people gave an argument based on Kruskal’s algorithm: that algorithm finds an MST
by repeatedly choosing the minimum-weight edge that does not create a cycle. Incrementing
each edge weight by 1 leaves the ordering of edge weights unchanged; therefore Kruskal’s
algorithm returns the same MST that it returned previously. The problem with this
argument is that it applies only to the particular MST returned by (some implementation
of) Kruskal’s algorithm, not to the collection of all MST’s. Thus, we only gave partial
credit for this argument.
Some people misinterpreted the question—after pointing out, correctly, that G need not
have a unique MST, they said that the MST could change if a randomized algorithm chose
a different MST for the new graph than for the original graph. But the question was
m
er as
whether the collection of MST’s can change. Other people said that the MST changes
trivially since the weights of its edges change. But the MST is defined by the collection of
co
eH w
edges in it, not the weights of those edges.
The second question was, if P is a shortest path from s to t in G, is P still necessarily
o.
the shortest path after every edge weight of G is incremented by 1? The answer is no.
rs e
Suppose, for example, that G consists of an edge from s to t of weight 1, and edges from s
ou urc
to a, a to b, and b to t each of weight 0. Then the shortest path is s → a → b → t, with
cost 0. But when we increment each edge weight by 1, the shortest path becomes s → t,
with cost 2.
o
Again, some people misinterpreted the question, and said the answer is no because the cost
aC s
of the shortest path changes trivially, even if the set of edges in the path does not change.
vi y re
Problem 3. There has been a lot of hype recently about Star Wars Episode II with the
release of the newest theatrical trailer. For this problem, suppose you are managing the
ed d
construction of billboards on the Anakin Skywalker Memorial Highway, a heavily-travelled
ar stu
stretch of road that runs west-east for M miles. The possible sites for billboards are given
by numbers x1 , x2 , ..., xn , each in the interval [0, M ] (specified by their position along the
highway measured in miles from its western end). If you place a billboard at location xi ,
is
you receive a revenue of ri > 0
You want to place billboards at a subset of the sites in {x1 , ..., xn } so as to maximize your
Th
total revenue, subject to the following restrictions:
1. Environmental Constraint. You cannot build two billboards within less than 5 miles
of one another on the highway.
sh
2. Boundary Constraint. You cannot build a billboard within less than 5 miles of the
western or eastern ends of the highway.
A subset of sites satisfying these two restrictions will be called valid.
Example Suppose M = 20, n = 4
{x1 , x2 , x3 , x4 } = {6, 8, 12, 14}
This study source was downloaded by 100000827039679 from CourseHero.com on 07-01-2021 10:22:31 GMT -05:00
https://www.coursehero.com/file/42774271/midterm2-solpdf/
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
m
The correct spelling of the TA’s names are Scott Aaronson, Shyam Lakshmin, Iordanis (Jordan)
er as
Kerenidis, Joseph (Joe) Polastre, Beini Zhou.
co
eH w
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
o.
last names.
rs e
ou urc
Problem 2. Consider a undirected graph G = (V, E) with nonnegative weights w(i, j) ≥
0 on its edges (i, j) ∈ E. Let s be a node in G. Assume you have computed the shortest
o
paths from s, and minimum spanning tree of the graph. Suppose we change the weights on
aC s
every edge by adding 1 to each of them. The new weights are w0 (i, j) = w(i, j) + 1 for every
vi y re
(i, j) ∈ 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.
ed d
(b) Would the shortest paths change due to the change in weights? Give an example
ar stu
where it changes or prove that it cannot change.
Solutions
is
The first question was, if T is a minimum spanning tree of a graph G, and if every edge
Th
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,
sh
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 with
This study source was downloaded by 100000827039679 from CourseHero.com on 07-01-2021 10:22:31 GMT -05:00
https://www.coursehero.com/file/42774271/midterm2-solpdf/
, Handout MS2: Midterm 2 Solutions 2
eb, we obtain a new spanning tree for the original graph with lower cost than T , since the
ordering of edge weights is preserved when we add 1 to each edge weight. This contradicts
the assumption that T was an MST of the original graph.
Many people gave an argument based on Kruskal’s algorithm: that algorithm finds an MST
by repeatedly choosing the minimum-weight edge that does not create a cycle. Incrementing
each edge weight by 1 leaves the ordering of edge weights unchanged; therefore Kruskal’s
algorithm returns the same MST that it returned previously. The problem with this
argument is that it applies only to the particular MST returned by (some implementation
of) Kruskal’s algorithm, not to the collection of all MST’s. Thus, we only gave partial
credit for this argument.
Some people misinterpreted the question—after pointing out, correctly, that G need not
have a unique MST, they said that the MST could change if a randomized algorithm chose
a different MST for the new graph than for the original graph. But the question was
m
er as
whether the collection of MST’s can change. Other people said that the MST changes
trivially since the weights of its edges change. But the MST is defined by the collection of
co
eH w
edges in it, not the weights of those edges.
The second question was, if P is a shortest path from s to t in G, is P still necessarily
o.
the shortest path after every edge weight of G is incremented by 1? The answer is no.
rs e
Suppose, for example, that G consists of an edge from s to t of weight 1, and edges from s
ou urc
to a, a to b, and b to t each of weight 0. Then the shortest path is s → a → b → t, with
cost 0. But when we increment each edge weight by 1, the shortest path becomes s → t,
with cost 2.
o
Again, some people misinterpreted the question, and said the answer is no because the cost
aC s
of the shortest path changes trivially, even if the set of edges in the path does not change.
vi y re
Problem 3. There has been a lot of hype recently about Star Wars Episode II with the
release of the newest theatrical trailer. For this problem, suppose you are managing the
ed d
construction of billboards on the Anakin Skywalker Memorial Highway, a heavily-travelled
ar stu
stretch of road that runs west-east for M miles. The possible sites for billboards are given
by numbers x1 , x2 , ..., xn , each in the interval [0, M ] (specified by their position along the
highway measured in miles from its western end). If you place a billboard at location xi ,
is
you receive a revenue of ri > 0
You want to place billboards at a subset of the sites in {x1 , ..., xn } so as to maximize your
Th
total revenue, subject to the following restrictions:
1. Environmental Constraint. You cannot build two billboards within less than 5 miles
of one another on the highway.
sh
2. Boundary Constraint. You cannot build a billboard within less than 5 miles of the
western or eastern ends of the highway.
A subset of sites satisfying these two restrictions will be called valid.
Example Suppose M = 20, n = 4
{x1 , x2 , x3 , x4 } = {6, 8, 12, 14}
This study source was downloaded by 100000827039679 from CourseHero.com on 07-01-2021 10:22:31 GMT -05:00
https://www.coursehero.com/file/42774271/midterm2-solpdf/
