COMP 3804: Assignment 3 Winter 2020 School of Computer Science Carleton University Due Date: Sunday, April 5th at 11:59PM Your assignment should be submitted online on CU Learn as a single PDF file. No late assignments will be accepted. You can type your assignment or you can upload a scanned copy of it. Please use a good image capturing device. Make sure that your upload is clearly readable. If it is difficult to read, it will not be graded! Question 1 [20 marks] Show how Bellman-Ford’s and Dijkstra’s algorithms would compute the shortest paths from A to all vertices of the graph shown in Figure 1. To show the execution steps of each of these algorithms, you must use the respective table format that we saw in class. Figure 1: The input graph for Question 1. Question 2 [20 marks] Consider the following linear program. minimize 4×1 + 6×2 subject to 2×1 + 3×2 ≤ 24 x1 − x2 ≤ 7 x2 ≤ 6 x1, x2 ≥ 0. • Show the feasible region by plotting the constraints on the (x1, x2)-Cartesian coordinate system. • Using your feasible region, find the optimal solution for this linear program. Is this the only solution? If yes, then explain why. If no, then state how many optimal solutions are there and justify your answer. 1 Question 3 [20 marks] A dietician wish to develop a diet using two foods F1 and F2. Each bag (containing 30g) of food F1 contains 12 units of calcium, 4 units of iron, 6 units of cholesterol and 6 units of vitamin A. Each bag (containing 30g) of food F2 contains 3 units of calcium, 20 units of iron, 4 units of cholesterol and 3 units of vitamin A. The diet requires at least 240 units of calcium, at least 460 units of iron and at most 300 units of cholesterol. The goal is to know how many bags of each food should the dietician use so as to minimize the amount of vitamin A in the diet. • (i) Formulate the problem as a linear program. • (ii) Similar to Question 2, solve the program by first plotting the constraints and then finding the optimal solution (i.e., how many bags of each food should be used). What is the minimum amount of vitamin A? • (iii) Verify your solution for Part (ii) by solving the program using an LP solver of your choice. You must state which solver you used and show the solution as produced by the solver. Question 4 [20 marks] Consider the reduction from 3-SAT to Independent Set. Given (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (z ∨ z) as an instance of 3-SAT, construct the instance of Independent Set. You do not have to give a true/false assignment. Just show the reduction diagram and explain it, illustrate the construction for this instance, and argue why the reduction works. Question 5 [20 marks] Consider the following decision problem on graphs, called BoundProblem. We are given an undi- rected graph G with n vertices and a list, called L, of n non-negative integers, as well a bound b. The problem is to determine if there is an assignment of the numbers in L to the vertices of G such that (i) each number is assigned to exactly one vertex of G and (ii) the sum of all the edge values, which is defined as the product of the values of its endpoints, is less than b. • Show that the BoundProblem is in NP. • Show that BoundProblem is NP-complete by showing that Vertex Cover reduces to Bound- Problem. • Suppose we do not allow zero-values. Does the problem remain NP-complete? Justify your answer. End of Assignment 3. 2
