Writing component

W1. [8 marks]

We will consider a variant of the safe set problem in which we are given a bound on the number of vertices we can select.

LIMITED SAFE SET MAXIMIZATION

Input: A graph G , with weight on edges and a positive integer k

Output: A safe set of maximum total value that uses at most k vertices

Unlike in programming question P1, where G is a simple path, we now consider the case in which G is a rooted tree. We can use the following definitions:

• U[i, j] is the maximum value of a safe set of size at most j that uses vertices in the subtree rooted at vertex i.

• R[i, j] is the maximum value of a safe set of size at most j that uses vertices in the subtree rooted at vertex i such that the root i is part of the safe set.

• N[i, j] is the maximum value of a safe set of size at most j that uses vertices in the subtree rooted at vertex i such that the root i is not part of the safe set.

For convenience, you may use w(i) as the weight of the vertex i and r as the root of the tree.

(a) [2 marks] What are the base cases and their values?

(b) [1 marks] Express U[i, j] in terms of smaller instances. You may also use R and N if you

wish.

(c) [2 marks] Express R[i, j] in terms of smaller instances. You may also use U and N if you

wish.

(d) [2 marks] Express N[i, j] in terms of smaller instances. You may also use U and R if you

wish.

(e) [1 mark] Give the expression that gives the answer to the problem.

 W2. [7 marks]

In this question you will prove an adversary lower bound on the problem ALL ZERO ROW OR COLUMN.

ALL ZERO ROW OR COLUMN

Input: A grid storing integers in each entry

Output: Yes or no, answering “Is there either a row or a column with all entries equal to zero?”

For your bound, you will consider only algorithms in which the key operation is specifying a row and column number and asking whether the data item in that entry is equal to zero. To make the problem simpler, we will assume that the input is an n x n grid.

(a) [3 marks] Describe an adversary strategy. Remember that an adversary can store and computer whatever it wishes, without worrying about limits on resources, but is unable to know what the algorithm is going to do next.

(b) [4 marks] State and prove the adversary lower bound in terms of n. For full marks, your bound must be a function in Ω(n^2)

 W3. [8 marks]

Using all the steps of the recipe shown in lecture, prove that SAFE SET DECISION, defined below, is in NP.

SAFE SET DECISION

Input: A graph G with positive edge weights and positive integers k and B.

Output: Yes or no, answering “Does G contain a safe set containing at most k vertices and with total value at lease B?

W4. [7 marks] Using the fact that INDEPENDENT SET is NP-complete, follow the steps in the recipe to show that SAFE SET DECISION is NP-complete.

Since the first two steps of the recipe have been completed, start your work at the third step.

 Programming component

For any of the programming questions in this assignment, you may import any of the following

files: check.py, equiv.py, and grids.py, as well as built-in modules such as math, itertools, and copy.

P1. [18 marks]

In this question, you will implement the dynamic programming algorithm for LIMITED SAFE SET MAXIMIZATION discussed in written question W1. We restrict our attention to graphs that form simple paths, represented as lists of integers. For example, the graph in the image would be implemented as [3, 5, 7, 8, 1, 6] .

Write a function safesetdp that consumes a nonempty list of positive integers vertices and a positive integer bound and produces the maximum value of a safe set of the graph of size at most bound. Your function must use dynamic programming. You may find it helpful to define C [i, j] as the maximum value of a safe set of size at most j that uses vertices in positions 0 through i.

For example, for the sample graph sample in the illustration, safesetdp(sample, 1) would produce 8, since the best choice of a single vertex is the vertex with weight 8, and

safesetdp(sample, 2) would produce 14, since the best choice is vertices with weights 8 and 6. Notice that it is not possible to select both the vertex of weight 8 and the vertex of weight 7. For full marks, you must use grids. To use the module grids.py, use the line from grids import *, do not include the code for grids.py directly in the file you submit.

Submit your work in a file with the name safesetdp.py.

P2 [7 marks]

In this question you will write a verification algorithm for ALL ZERO ROW OR COLUMN.

Write a function verify_all_zero that consumes a grid instance and a certificate. You cannot make any assumptions about the type of certificate.

Your function should produce True if certificate is a list of length two, where the first item in the list is the string "row" or the string "column" and the second item in the list is an integer i, and the following hold, and False otherwise:

• If the first item is "row", then row i contains all zeroes.

• If the first item is "column", then column i contains all zeroes.

To see how the function works, suppose my_grid is the following grid:

0 01 0

1 00 1

0 00 0

Then verify_alLzero(my_grid, ["column", 1]) will produce True, since there is a zero in every position in column 1, but verify_alLzero (my_grid, ["row", 0) will produce False, since there is a 1 in row O and column 2.

Submit your work in a file with the name verifyallzero .py.