程序代写案例-COMP3011-Assignment 4

THE HONG KONG POLYTECHNIC UNIVERSITY Fall 2020
COMP3011: Design and Analysis of Algorithms
Assignment 4
Due: Monday, 07 December 2020, 3:30 p.m.
To submit the assignment, upload a .pdf-, .doc-, .docx-, .txt-, or .jpg-file with your solutions to Black-
board before the deadline. The filename should start with “A4 99999999Z” (replace “99999999Z” by
your student ID number). Include your name and student ID number at the top of each page. Scanned,
handwritten solutions are OK as long as they are easily readable. You may specify your algorithms in
pseudocode or in plain English.
The maximum possible score is 15 marks. Late submissions will not be accepted. The assignment is to
be completed individually, i.e., every student must turn in his or her own solutions. Students are allowed
to discuss solution strategies with other students but they are not allowed to copy each others’ answers.
1. In this question, consider the two algorithms for computing convex hulls named Graham’s scan
(the Merge-Sort-based implementation) and Jarvis’s march that were presented in Lecture 10.
Show how to define, for every positive integer n ≥ 3, a sequence of n points in the plane for which
Jarvis’s march is asymptotically faster than Graham’s scan. Also, explain why Jarvis’s march is
faster in this particular case. (2 marks)
2. Three points in the plane are called collinear if they lie on the same straight line. For example,
the three points (0, 1), (1, 3), (3, 7) are collinear. Describe an algorithm that solves the following
problem efficiently and analyze its time complexity.
Input: A sequence Q of points in the plane.
Output: “YES” if Q contains three points that are collinear; “NO” otherwise.
Let n denote the number of points in the input, i.e., n = |Q|. To get full marks, the worst-case
running time of your algorithm must be O(n2 lg n). Note that two or more points in the input Q
may have the same coordinates. (3 marks)
3. Let Independent-Set and U-LCS be the two decision problems defined below. U-LCS is “un-
bounded” in the sense that the number of input sequences as well as the size of the alphabet that
the symbols belong to can be arbitrarily large and are not fixed in advance.
Independent-Set:
Input: A positive integer k and an undirected graph G with vertex set V and edge set E.
Output: “YES” if there exists a subset S of V with |S| ≥ k such that no two vertices in S are
adjacent in G; “NO” otherwise.
The Unbounded Longest Common Subsequence Decision Problem (U-LCS):
Input: A positive integer ` and a set X of sequences of symbols.
Output: “YES” if there exists a common subsequence of X of length ≥ `; “NO” otherwise.
Independent-Set is known to be NP-complete (you do not need to show it here). Prove that
U-LCS is NP-complete. (3 marks)
4. According to question 3. above, Independent-Set isNP-complete. Is the restriction of Independent-
Set to instances in which the input graph G has no cycles of length 3 still NP-complete? If yes,
give a proof; if not, describe a polynomial-time algorithm that solves it. (3 marks)
(Continued −→)
1
5. If P 6= NP, would it be possible for a decision problem to belong to P and also be NP-complete?
Justify your answer. (1 mark)
6. Define the following optimization problem.
Input: A connected, undirected graph G.
Output: An assignment of a direction to each edge in G such that the number of vertices with
at least one outgoing edge is as small as possible.
As an example, if the input is the undirected graph on the left then the directed graph on the
right is an optimal solution. It has three vertices with at least one outgoing edge, and this is the
minimum possible because it’s impossible to assign directions to all the edges so that only two
vertices get outgoing edges.
Describe a polynomial-time 2-approximation algorithm for the problem. Prove that your algo-
rithm’s approximation ratio is at most 2 and that it runs in polynomial time.
Hint: Use one of the approximation algorithms that was presented during the lectures. (3 marks)
2

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie