Assignment 5- We are given a set of points

Assignment 5
1. [22 marks] Programming question. We are given a set of points P = {p1,...,pn} in two dimensions and two vertices s,t ∈ P. Write a program to find a path pi0,pi1,...,pi` ∈ P with pi0 = s and pi` = t that minimizes the largest edge distance along the path, i.e., minimizes max{d(pi0,pi1),d(pi1,pi2),...,d(pi`−1,pi`)}, where d(p,q) denotes the Euclidean distance between p and q. Note that this is different from the standard shortest path problem, because the goal is to minimize the largest edge distance, not the sum. Also note that the answer may not be unique; your program can return any optimal path. For point set P = {p1 = (x1,y1),...,pn = (xn,yn)}, the input to your program is given in the following format, where the xi’s and yi’s are all integers:
n x1 y1 x2 y2 . . . xn yn
The vertex s is the first point (x1,y1) and the vertex t is the second point (x2,y2) in the input. The output to your program should have the following format:
i0 i1 . . . i`
where pi0,pi1,...,pi` denotes an optimal path. (We always have i0 = 1 and i` = 2, because s = p1 and t = p2. The index values i0,i1,...,i` are all in {1,...,n}.) Your program should run in O(n2) time. The recommended approach is as follows: compute the minimum spanning tree (MST), and just return the path from s to t in the MST! (You don’t have to prove correctness of this approach.) To compute the MST, I would suggest you implement Prim’s algorithm in the simple version without special data structures (you don’t need heaps, and you don’t even need to explicitly build adjacency lists or adjacency matrices). Hand in a printed copy of your program and electronically submit the source file, named a5.cpp or a5.java. Do experiments on the runtime and describe (on paper) how your input is generated, present the results in a table or graph, and briefly comment on whether the experimental results agree with the theoretical analysis. (You do not need to submit your input-generating program.)
1
2. [16 marks]
(a) [7 marks] Convert the following optimization problem into a decision problem and show that the corresponding decision problem is in NP: Input: n positive integers a1,...,an, a number k, and a positive integer W. Output: a subset S ⊆{1,...,n}with|S| = k minimizing the value? ?Pi∈S ai −W? ?.(b) [ 4 marks] Show that if we could solve your decision problem in (a) in time polynomial in the number of input bits, then we could also compute the minimum value in time polynomial in the number of input bits.
(c) [5 marks] Show that if we could solve your decision problem in (a) in time polynomial in the number of input bits, then we could also compute an optimal subset S itself in time polynomial in the number of input bits. [You may use part (b) as a subroutine.]
3. [22 marks] Consider the following decision problem Multiple-Shortest-Paths (MSP):
Input: An unweighted, directed graph G = (V,E), integers K and L, and K pairs of vertices (s1,t1),...,(sK,tK). Output: “yes” iff there exist paths p1,...,pK, where pi goes from si to ti, such that no two paths share a common vertex and the total number of edges in these paths is at most L.
(a) [5 marks] Prove that MSP is in NP.
(b) [13 marks] Prove that MSP is NP-complete via a polynomial-time reduction from 3SAT to MSP. Hint: For each clause Ci = αi1 ∨αi2 ∨αi3, create 5 vertices si,vi1,vi2,vi3,ti and add appropriate edges to form 3 length-2 paths from si to ti... Whenever there are two opposite literals αij = αi0j0, create 2 vertices siji0j0,tiji0j0 and add appropriate edges to form 2 length-2 paths from siji0j0 to tiji0j0...And define L and K appropriately... (c) [4 marks] Illustrate your reduction on the following 3SAT example:
(x1 ∨x2 ∨x3) ∧ (x1 ∨x3 ∨x4) ∧ (x2 ∨x3 ∨x4). Draw the resulting graph, and specify the value of L and K and the pairs of s’s and t’s. Draw a solution (a set of paths) that corresponds to the following satisfying assignment: x1 = 1, x2 = 0, x3 = 0, x4 = 1.
2