这个作业是完成算法测试题：NP问题、贪婪算法等

COM2109/COM2001/COM21001

1. a) Which of the following statements are true; which ones are false?

(i) Let X be an NP-complete problem and let Y be an NP-hard problem. Then

there is a polynomial-time reduction from X to Y .

(ii) If P6=NP, then there is no polynomial-time algorithm for the Hamiltonian

Cycle problem.

(iii) Let X be an NP-complete problem and let Y be an NP-hard problem. Then

there is a polynomial-time reduction from Y to X.

(iv) If there is a polynomial-time algorithm for the Satisfiability problem, then

there is a polynomial-time algorithm for the Knapsack problem.

[20%]

b) (i) Write a function OptimumKnapsack in Pseudo-code that, given an instance I

of knapsack (having n items with values v1, . . . , vn, weights w1, . . . , wn, and

capacity C), finds the maximum total value V such that I has a solution of

value V . The function is required to run in polynomial-time but can make calls

to a function DecideKnapsack(I, V ) that, given an instance I of Knapsack

and a total value V , returns true if I has a solution of total value at least V

and otherwise false.

Hint: You can use the function BinarySearch(l, u) that, given integers l and

u uses binary search to find the largest value V between l and u such that

DecideKnapsack(I, V ) returns true. [10%]

(ii) Argue why the following “solution” to the above problem is not correct!

OptimumKnapsack( I )

V=0

while DecideKnapsack( I, V )

V ← V + 1

return V − 1

Hint: The function returns the correct value but is not correct for a different

reason. [10%]

QUESTION CONTINUED ON THE NEXT PAGE

” TURN OVER

COM2109/COM2001/COM21001

c) Consider the following problem:

Magic Set

Instance: A set S, a family (set) M ⊆ 2

S of subsets of S and an integer k.

Parameter: k.

Question: Does S contain a magic set D ⊆ S containing at most k elements? A

magic set is a set D ⊆ S such that D enchants all sets in M, i.e., M ∩ D 6= ∅ for

every set M ∈ M.

Example: Let S = {1, 2, 3, 4, 5} and let M consists of the sets M1 = {1, 2, 3},

M2 = {4, 5}, and M3 = {3, 4}. Then:

• the elements 1 and 2 enchant only the set M1,

• the element 3 enchants the sets M1 and M3 (but not M2),

• the element 4 enchants the sets M2 and M3 (but not M1),

• the element 5 enchants only the set F2,

• the set {3, 4} is a magic set for the instance of size 2, and there is no magic set

of size 1.

(i) Write a function FindMagicSet in Pseudo-code that, given an instance I =

(S,M, k) of the Magic Set problem finds a magic set for I of size at most

k (you can assume that I is a Yes-instance). The function is required to run

in polynomial-time but can make calls to the function DecideMagicSet that,

given an instance of the Magic Set problem returns true if the instance is

a Yes-instance and false otherwise. [20%]

Hint: Use the notation M[u] to denote the set of all sets in M that contain

u.

(ii) Show that the Magic Set problem is in NP.

Hint: A potential solution/witness to the Magic Set problem is a subset of

S of size at most k. [20%]

(iii) Show that the Magic Set problem is in NP-hard.

Hint: Use a polynomial-time reduction from Vertex Cover. [20%]

” CONTINUED

COM2109/COM2001/COM21001

2. Consider the graph G illustrated in the following picture.

1

3 2

4

5 7

6

8 9

10

a) Calculate a lower bound for the size of a vertex cover of G obtained from a maximal

matching and specify both the maximal matching and the obtained lower bound. [10%]

b) Calculate an upper bound for the size of a vertex cover (and the corresponding vertex cover) using the greedy algorithm (based on maximum degree) from the lecture.

Resolve ties (i.e., if there is more than one vertex with the same degree) using the

natural order on the natural numbers (or lexicographical order). Specify the obtained

vertex cover and its size. [10%]

QUESTION CONTINUED ON THE NEXT PAGE

” TURN OVER

COM2109/COM2001/COM21001

c) Apply the branch-and-bound algorithm without degree-two rule for the Vertex

Cover problem that was presented in the lecture (recall that the lower bound is

computed using a maximal matching and the upper bound is computed using a greedy

algorithm that always chooses a vertex of maximum degree) to G using the depthfirst strategy (recursing first on the node corresponding to the chosen vertex and

then recursing on the node corresponding to the neighbours of the chosen vertex) for

the choice of the next subproblem/subinstance. Draw a possible branch-and-bound

tree similar to the template given below. Provide the following for each node of the

branch-and-bound tree:

• a number corresponding to the step of the algorithm at which the node is considered,

• the remaining graph G0

,

• the current (already fixed) partial vertex cover (C),

• the value of the (local) lower bound L together with the maximal matching M

used to compute the lower bound,

• the value of the (local) upper bound U together with the vertex cover V (on the

remaining graph G0

) used to compute the upper bound.

Alternatively specify that the node does not correspond to a valid partial solution and

state the reason why this is the case. Also specify the branching decision that an edge

corresponds to at each edge of the branch-and-bound tree.

Always (i.e., for the greedy upper bound algorithm and for the choice of the next

vertex to branch on), resolve ties (i.e., more than one vertex with the same degree)

using the natural order on the natural numbers (or lexicographical order).

Tip: Try to always find a maximum matching (instead of a matching that is merely

maximal) as this can reduce the size of the branch-and-bound tree.

Step: 1

G

∅

L =?

M

U =?

V

Step: ?

G0

C

L =?

M

U =?

V

Step: ?

G0

C

L =?

M

U =?

V

N[v]

some vertex v

Example template for the branch-and-bound tree.

[70%]

d) Specify one node in the branch-and-bound tree, where an optimal vertex cover is found

and provide the obtained optimal vertex cover together with its size. [10%]

” CONTINUED

COM2109/COM2001/COM21001

3. a) Invoke the FindTour algorithm for the travelling salesman problem (TSP) on the

following 4-vertex graph G. Answer the following questions.

a

c b

d

2

4

5

3

6

2

(i) What is the minimum spanning tree T of G? [20%]

(ii) Write down an Eulerian tour of the graph that is obtained by duplicating edges

in T. [20%]

(iii) Write down the TSP tour output by the algorithm FindTour. [20%]

b) In a lab, 80 robots sit peacefully in a circle. Suddenly, each robot randomly attacks

the robot immediately to its left or right. What is the expected number of unattacked

robots? Justify your answer. [40%]

” TURN OVER

COM2109/COM2001/COM21001

4. a) Suppose we have a randomised algorithm Alg that outputs a number R such that

with probability 3

4

it holds that R is in the interval [1, 10], i.e., 1 ≤ R ≤ 10.

(i) If we run the algorithm Alg twice, what is the probability that at least one

of the numbers R1, R2 returned is in the interval [1, 10]? Justify your answer.

[20%]

(ii) If we run the algorithm Alg thrice, what is the probability that at least two of

the three numbers R1, R2, R3 returned are in the interval [1, 10]? Justify your

answer. [40%]

b) Let Alg be a randomised algorithm for the PRIME problem, i.e., to decide if an

integer is prime or not. Suppose that Alg runs in expected polynomial time and

always outputs the correct answer.

Use Alg to give a new randomised algorithm NewAlg for the PRIME problem such

that NewAlg always runs in polynomial time and

• if the input integer is prime, then it will be accepted with probability at least 5

6

;

• if the input integer is not prime, then it will always be rejected.

Describe your algorithm and justify its correctness and running time. [40%]

Hint: You may use Markov’s inequality: If X is a random variable assuming only

non-negative values, then for any positive real number t, it holds that

Pr[X ≥ t] ≤

E[X]

t

.

END OF QUESTION PAPER

“

**程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持 Alipay WeChatPay PayPal等支付方式

**E-mail:** vipdue@outlook.com **微信号:**vipnxx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。