Homework 8 COMS 311 Points: 100 Due: Nov 20, 11:59PM
1. You are in a rectangular maze organized in the form of M × N cells/locations. You are starting at the upper left corner (grid location: (1, 1)) and you want to go to the lower right corner (grid location: (M,N)). From any location, you can move either to the right or to the bottom, or go diagonal. I.e., from (i,j) you can move to (i,j + 1) or (i + 1,j) or to (i + 1, j + 1). Cost of moving right or down is 2, while the cost of moving diagonally is 3. The grid has several cells that contain diamonds of whose value lies between 1 and 10. I.e, if you land in such cells you earn an amount that is equal to the value of the diamond in the cell. Your objective is to go from the start corner to the destination corner by picking up diamonds such that the difference between the sum of the value of diamonds you picked and sum of the costs incurred is maximized.
Write a dynamic programming algorithm to solve the above problem. State the recurrence relation and design iterative algorithm based on the recurrence. Your algorithm should not be recursive. State the runtime of your algorithm.
Ans. Let Z denote the rectangle grid. Let V [i][j] denote the value of the diamond at Z[i][j]. Let P[i][j] denote the maximum possible earnings when we start at Z[1][1] and end at Z[i][j]. Our goal is to compute P[M][N]. How can we arrive at Z[M][N]? We can come from Z[M − 1][N] or Z[M][N − 1] or from Z[M − 1][N − 1]. Thus the best way to reach Z[M][N] is the best of the following three: Find the best possible way to come to Z[M −1][N] and go to Z[M][N] or find the best path to Z[M][N − 1] and go to Z[M][N], or find the best path to Z[M − 1][N − 1] and go to Z[M][N]. This gives us the following recurrence.
P[i−1][j]+V[i][j]−2
P[i][j] = max P[i][j − 1] + V [i][j] − 2 (1)
P[i−1][j −1]+V[i][j]−3
Using this we arrive the following iterative algorithm. Note that P [1][1] = V [1][1]. The only way to arrive at Z [1][i] is by taking i − 1 steps to the right which incurs a cost of 2(i − 1) and and gain of ij=1 V [1][j]. Thus
i
P [1][1] = V [1][j] − 2(i − 1) j=1
1
Similarly
i
P [i][1] = V [j][1] − 2(i − 1) j=1
Thus we initialize the first row and first column of P as above. Now for every 2 ≤ i ≤ M and for2≤j≤N weset
P[i−1][j]+V[i][j]−2
P[i][j] = max P[i][j − 1] + V [i][j] − 2 (2)
P[i−1][j −1]+V[i][j]+3 Finally we output P[M][N]. Clearly the runtime is O(MN).
2. Suppose to build RSA crypto system you picked primes p and q as 3 and 7 and e as 5 what are the public and private keys? What is the encryption of a message whose integer equivalent is 12. Show that the decryption gives back the message 12.
Ans. (p − 1)(q − 1) = 12. The private key d should satisfy the property (ed − 1)%12 equals zero. Sincee=5,wegetd=5.
Enc(12) = 125mod21 = 3 Dec(3) = 35mod21 = 12
3. Similar to Problem 6.10 from text, with three machines instead of two machines. You have 3 machines A,B and C. During time interval i machine A can process ai TB of data, B can process bi TB of data and C can process ci TB of data. At any time, you are allowed to use only one machine. If during time step i, you are running a machine, say A, in the next time step i + 1, you can chose between running the machine A or switch to B or C. Switching takes one unit of time, and thus if you decide to switch then no data is processed during time step i + 1. Your goal is to arrive an optimal schedule of machines that maximizes the total amount of data processed. If n = 9, an example schedule may look like [A, SwitchT oB, B, B, SwitchT oA, A, SwitchT oC, C, C]
Write a dynamic programming based algorithm that gets three arrays A = [a1, · · · , an], B = [b1,··· ,bn], C = [c1,···cn] as inputs and outputs the total amount data processed by an optimal schedule.
Ans.
Say OPT[A,i] is the optimal amount of data processed in i time steps, when the A is used in time step i. Define OPT[B,i] and OPT[C,i] simialrly.
Let us analyze OP T [A, i]. Now at Time step i − 1, there are three possibilities: Use machine A, Switch from B and thus use machine B at time i − 2 or Switch from C and thus use machine C at time i − 2. Thus
OP T [A, i] = max{OP T [A, i − 1] + ai, OP T [B, i − 2] + ai, OP T [C, i − 2] + ai} 2
OP T [B, i] = max{OP T [A, i − 2] + bi, OP T [B, i − 1] + bi, OP T [C, i − 2] + bi} OP T [C, i] = max{OP T [A, i − 2] + ci, OP T [B, i − 2] + ci, OP T [C, i − 1] + ci}
This gives following iterative algorithm: Initialize OP T [A, 1] to a1. OP T [B, 1] to b1 and OPT[C,1] to c1. Initialize OPT[A,2] to a1 + a2, OPT[B,2] to b1 + b2 and OPT[C,2] to c1 + c2.
for (i = 3 to n ) {
OPT[A, i] = a_i +max{OPT[A, i-1], OPT[B, i-2], OPT[C, i-2]}
OPT[B, i] =b_i+max{OPT[A, i-2], OPT[B, i-1] OPT[C, i-2]}
OPT[C, i] = c_i + max{OPT[A, i-2] , OPT[B, i-2], OPT[C, i-1]}
}
Return max{OPT[A,n], OPT[B, n], OPT[C, n]}
4. Given an undirected graph G = (V, E). A set S ⊆ V is a dominating set if every vertex v ∈ V either belongs to S or is adjacent to a vertex in S. Show that the following decision problem is in NP.
Problem: Dominating Set
Input Instance: Undirected graph G.
Decision: Is there a dominating set of size ≤ n/4 in G?
Ans. Consider the following interaction between prover and verifier on inputs G and n/4. Witness: Here is a set S ⊆ V . Verification Algorithm A verifies the following conditions and
outputs “yes” if and only if all the conditions are verified:
• Verify that the size of S is ≤ n/4.
• For every vertex v verify if at least one of the following conditions hold.
–v∈S
– The set Nv = {u | ⟨u,v⟩ ∈ E} and the set S have at least one common element.
Time taken by the verification Algorithm: First step takes O(n) time. Checking whether v ∈ S takes O(n) time (as size of S is at most k). Computing the set Nv sets O(n) time. Checking whether Nv and S have a common element takes O(|S||Nv) time. Note that the
3
size of Nv is at most n. Thus every iteration of the loop takes at most O(n2) time. Thus the total time taken by the algorithm is O(n3) which is polynomial is the size of the graph.
Note that if the graph has a dominating set of size ≤ n/4, there exists a set S of size ≤ n/4 such that every vertex of G either belongs to S or is adjacent to a a vertex in S. Such a set S is the witness and the verification algorithm outputs “Yes” given this witness as input. However, if the graph does not have a dominating set of size ≤ n/4, then for every S, either the size of S is more than k or for some vertex v neither v nor its neighbors belong to S. Thus for every witness S the verification algorithm outputs “No”.
Finally, the size of the proof given by the prover is is O(n) which is polynomial in the size of the graph. This shows that Dominating Set is in NP.
5. Given an undirected graph G = (V,E), let N(v) = {u | ⟨v,u⟩ ∈ E}. Given a set of vertices S ⊆ V , let N(S) = ∪v∈SN(v). An undirected graph G is c-magical, if for every set S ̸= ∅ with |S| ≤ |V |/3, |N(S)| ≥ (1 + c)|S|. Show that the following decision problem is in NP.
Input: Undirected Graph G Decision: Is G not 1/4-magical.
Ans. Witness: A set S
Verification Algorithm A verifies the following conditions and outputs “yes” if and only if all the conditions are verified:
• Verify that |S| is atmost n/3.
• For every v ∈ S, compute N(v).
• Compute T = ∪v∈SN(v).
• Verify that the size of T is less than 3n/4.
Suppose that G is not 1/4 expander. Then there is a non-empty subset S for which N(S) has less than 3n/4 elements. In thus case, witness is S and the verification algorithm outputs “yes”. If G is a1/4 expander, then for every nonempty set S of size ≤ n/3, the size of N(S) is at least 3n/4. Thus for every witness S, the verification algorithm outputs “No”.
The set S can have at most n elements. Thus the size of S is polynomial in n.
Now we claim that verification process takes polynomial time. Verifying of |S| ≤ n/2 takes O(n) time. We can compute the set N(v) by looking at the adjacency list of v. This takes at most O(m) time. Finally, we need to compute the union of N(v) for all v ∈ S. Note that size of S is at most n/3 and the size of N(v) is at most n. Thus we need to compute the union of n/3 lists each of size at most n. We can sort the lists and use a merge algorithm to compute the union, Each merge operation takes O(n) time. Thus the time taken to compute the union can be bounded by O(n3). Verifying if the size of the union is less than 3n/2 takes O(n) time. Thus the total time taken by the verifier is bounded by O(n3) which is polynomial.
4