Description
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.
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.
(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.
2
