COMP3011-Assignment 4 Solved

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.    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 lgn). Note that two or more points in the input Q may have the same coordinates. 

3.    Let Independent-Set and U-LCS be the two decision problems defined below. U-LCS is “unbounded” 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. 

4.    According to question 3. above, Independent-Set is NP-complete. Is the restriction of IndependentSet 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. 

(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 algorithm’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.       

2