CS 560代写、代做C/C++程序语言、代写c++代写、代做Algorithm

日期：2019-11-21 11:46

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])

sw = f alse ;

k = n ;

repeat

sw = f alse ;

for i = 1 to k − 1 do

if A[i] > A[i + 1] then

Swap A[i] and A[i + 1] ;

sw = true ;

end

end

k = k − 1;

until sw = false;

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

0v

0 ∈ 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.