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 4x1 + 6x2
subject to 2x1 + 3x2 ≤ 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