# 算法代写 | COM2109/COM2001/COM21001

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
” 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
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
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 E-mail: vipdue@outlook.com  微信号:vipnxx 