首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- Comp201作业代做、Software Engineering作业代写、J 2019-12-07
- Comp3322a作业代做、代写modern Technologies作业、 2019-12-07
- Cse315留学生作业代写、代做software Engineering作业 2019-12-07
- 代写cse403留学生作业、代做java程序语言作业、System课程作业代 2019-12-07
- Cse-381作业代做、代写canvas留学生作业、代做c++语言作业、C+ 2019-12-07
- Stat 315作业代写、Linear Relationship作业代写、代 2019-12-07
- Cs602留学生作业代做、代写programming课程作业、代做pytho 2019-12-07
- Math5714作业代做、代写linear Regression作业、R编程 2019-12-07
- Ista 116作业代写、Data留学生作业代做、代写r程序设计作业、R语言 2019-12-07
- 代做data留学生作业、代写r编程语言作业、代做r课程设计作业代写r语言编程 2019-12-07
- Sehs3321作业代做、代做web，Html编程语言作业、代写networ 2019-12-07
- Stat2005作业代写、代做r编程设计作业、代写programming课程 2019-12-07
- 代做data Set作业、代写python，Java编程语言作业、代做c/C 2019-12-07
- Cis 212留学生作业代做、代写c/C++编程设计作业、代做c/C++语言 2019-12-06
- 代做csi 403留学生作业、Data Structures作业代写、代做j 2019-12-06
- 代做bpi889留学生作业、代写r编程语言作业、R课程设计作业代做、Data 2019-12-06
- 代写website留学生作业、代做python程序设计作业、代写python 2019-12-06
- Comp201作业大写、代做software Engineering作业、代 2019-12-06
- Game Srs作业代做、代写linux Platforms作业、Java编 2019-12-06
- 代写stat 462/862作业、代做python编程设计作业、代写java 2019-12-06