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