CS 560, HOMEWORK 4 SOLUTIONS
INSTRUCTOR: HOA VU
Each question is worth 25 points. The extra credit question is worth 10 points.
When you are asked to design an algorithm, do the following: a) describe the algorithm,
b) explain (or more rigorously prove) why it is correct, and c) provide the running time.
Unless specified otherwise, the problems are from the textbook by Jeff Erickson.
(1) Question 1: Consider the bubble sort algorithm: BubbleSort(A[1 . . . n])
Algorithm 1: Bubblesort
In each iteration of the outermost loop, we scan through the array, if there is
a consecutive pair of entries that is in the wrong order, we swap them. We stop
when there is no swap, i.e., the array is sorted.
Part a) After the first iteration of the outermost loop, why must the largest element
ends up being in A[n]? After the second iteration of the outermost loop, why
must the second largest element ends up being in A[n−1]. What is the generalized
observation after the ith iteration of the outermost loop? Then conclude that after
the nth iteration of the outermost loop, A is sorted.
In the first iteration, the largest element will keep being swapped until it reaches
A[n]. Similarly, in the second iteration, the second largest element will keep being
swapped until it reaches A[n − 2], and so on. The generalized observation is that
1
2 INSTRUCTOR: HOA VU
after the ith iteration, the ith largest element will be at A[i]. Therefore, after the
n, iteration, the array is sorted.
Part b) What is the running time of the algorithm. Please justify your answer.
The algorithm runs in O(n
2
) time. Each inner loop runs at most O(n) times
(since k ≤ n). After each outer loop’s iteration, another entry will be in the right
place in A. Hence, the outer loop runs at most O(n) times. Thus the total running
time is O(n
2
).
(2) Question 2: Given anl array A[1 . . . n] of numbers (that are not necessarily positive).
Design an algorithm that rearranges the entries in
P
A to maximize the sum. Make sure you prove that your algorithm maximizes the described
sum.
The algorithm is to simply sort A in non-decreasing order. Claim: in the optimal
arrangement A[i] ≤ A[i + 1] for all 1 ≤ i ≤ n − 1. The proof by contradiction is as
follows. Suppose A[i] > A[i + 1] for some i. Then let x = A[i] and y = A[i + 1].
Note that x > y as assumed. If we swap A[i] and A[i + 1]. Then the sum changes
by an amount:
iy + (i + 1)x − ix − (i + 1)y > 0 ⇐⇒ x − y > 0 ⇐⇒ x > y.
Hence, we get an arrangement with a larger sum and therefore, the arrangement is
not optimal. Thus, we have a contradiction. Hence, in the optimal arrangement,
the order must be non-decreasing.
(3) Question 3: Problem 1a page 268. For simplicity, assume all weights are distinct.
To prove it, follow the following steps. Let uv be the edge with the largest weight
in the cycle C. In particular, w(uv) > w(u0v0) for all other u
0v0 ∈ C.
Step 1) Suppose uv is in the minimum spanning tree (MST) T∗
If you delete uv
from the MST T∗, you will have two connected components A and B where u ∈ A
and v ∈ B. Argue why there must be an edge ab 6= uv in C that has one end point
in a ∈ A and one end point b ∈ B (feel free to draw a picture to visualize).
Step 2) Argue that T = T
∗ − {uv} + {ab} is also a spanning tree but with a
smaller weight. Deduce a contradiction and conclude that uv cannot be in an MST.
Suppose uv is in the cycle C = v, u, x1, x2, . . . , xk and uv has the largest cost
and suppose uv ∈ T
∗
for some MST T
∗
.
If you delete uv from T
∗
, there must be two connected trees A and B where
u ∈ A and v ∈ B. We know that u, x1, . . . , xk, v is a path from u to v. In this
path, there must be an edge xixi+1 between a node in A and a node in B. Now,
T − {uv} + {xixi+1} is also a spanning tree (since A and B are trees that are not
connected to each other, by adding xixi+1, you connect A and B and therefore
have a spanning tree) with a smaller weight since w(xixi+1) < w(uv). Thus, we
have a spanning tree with a smaller weight than T
∗ which contradicts with the
assumption that T
∗
is an MST. Thus, uv must not be in an MST.
CS 560, HOMEWORK 4 SOLUTIONS 3
(4) Question 4: Suppose a graph G has n nodes where n is even. Furthermore, every
node in G has degree (degree of a node is the number of edges that node is incident
on) at least n/2. Prove that G is connected or give a counter-example to disprove
the claim.
Suppose for contradiction that G has the described property and is disconnected.
Then, pick a vertex v in G. Let S be the set of nodes reachable from v. We know
that V \ S 6= ∅ (in other words, there are nodes not in S), otherwise, the graph
is connected. Now, since the total number of nodes is n, either S or V \ S has at
most n/2 nodes.
In the case that S has at most n/2 nodes, consider v, by our assumption, it is
connected to at least n/2 edges but it can have at most n/2 − 1 neighbors in S.
Hence, it must be connected to another node in V \S. This leads to a contradiction,
since then there is a path from v to another node in V \ S contradicting the fact
that S is the set of all reachable nodes from v.
In the case that V \S has at most n/2 nodes, again, consider any node u ∈ V \S.
By our assumption, it is connected to at least n/2 edges but it can have at most
n/2 − 1 neighbors in V \ S. Hence, it must be connected to another node w in S.
This leads to a contradiction, since then there is a path from v to w and since wu
is an edge, there is a path from v to u contradicting the fact that S is the set of all
reachable nodes from v.
(5) Extra credits: Problem 3 page 178.
The (greedy) algorithm is as follows. Assume X = [a, b]. Originally, we pick the
set that starts at a and covers as much to the right as possible. Call this set S1.
Let the sets we picked so far be S1, . . . , Si
. We pick Si+1 that starts before Si ends
and goes furthest to the right. We can implement the algorithm in O(n log n) time
by first sorting the sets according to the ending point. To add Si+1, we can binary
4 INSTRUCTOR: HOA VU
search among the remaining sets for the set that starts at a point before Si ends
and goes furthest to the right. In particular, it takes O(log n) time to figure out
Si+1.
Proof of correctness: We prove by induction that after the ith step, the solution
{S1, . . . , Si} is part of some optimal solution. Clearly, after the 0th step, the solution
is an empty set which is a subset of the optimal solution. Induction hypothesis:
suppose {S1, . . . , Si} is part of some optimal solution T = {T1, T2, . . .}. Let the ordering
of Ti
’s be such that if Ti+1 = [a, b] and Ti = [c, d] then b ≥ d. Observe that
then T1 = S1, T2 = S2, . . . , Ti = Si
. Now, if we have covered the entire desired
interval X then we are done since we know that S1, . . . , Si
is an optimal solution.
Otherwise, the algorithm then picks Si+1 that goes furthest to the right. Therefore,
for any remaining set (not yet picked by the algorithm) R:
(S1 ∪ . . . Si) ∪ R ⊆ (S1 ∪ . . . Si) ∪ Si+1. (∗)
We need to show that {S1, . . . , Si
, Si+1} is also part of some optimal solution.
Suppose not. Then, consider Ti+1 in T. Ti+1 must start no later than where Ti ends.
Note that the algorithm considered both Ti+1 and Si+1 at the (i+ 1)th step. Based
on (∗), if we remove Ti+1 from T and add Si+1 to T, we still have a collection of the
same number of sets that covers the entire X. Hence, {S1, . . . , Si
, Si+1} is also part
of some optimal solution which is a contradiction. Therefore, {S1, . . . , Si
, Si+1} is
also part of some optimal solution.