CS161-Homework 6 Solved

1.   Consider the graph below:

 

Step through the Floyd-Warshall algorithm on this graph (using the order suggested by the vertex labels), and write down what your tables D(i) look like for i = 0,1,2,3. (You may either code this up or do it by hand).

If it helps, here is the LATEXcode for one such table:

\begin{tabular}{c|c|c|c|}

$D^{(i)}$ & 1 & 2 & 3 \\ \hline

1    & - & - & - \\ \hline

2    & - & - & - \\ \hline

3    & - & - & - \\ \hline

\end{tabular}

2.   Let A be an array of length n containing real numbers. A longest increasing subsequence (LIS) of A is a sequence 0 ≤ i1 < i2 < ...i` < n so that A[i1] < A[i2] < ··· < A[i`], so that ` is as long as possible. For example, if A = [6,3,2,5,6,4,8], then a LIS is i0 = 1,i1 = 3,i2 = 4,i3 = 6 corresponding to the subsequence 3,5,6,8. (Notice that a longest increasing subsequence doesn’t need to be unique).

In the following parts, we’ll walk through the recipe that we saw in class for coming up with DP algorithms to develop an O(n2)-time algorithm for finding an LIS.

(a)    (We’ll come up with the sub-problems and recursive relationship for you, although you will have to justify it. Let D[i] be the length of the longest increasing subsequence of [A[0],...,A[i]] that ends on A[i].

Explain why

D[i] = max({D[k] + 1 : 0 ≤ k < i,A[k] < A[i]} ∪ {1}).

(b)   Use the relationship about to design a dynamic programming algorithm returns the length of the longest increasing subsequence. Your algorithm should run in time O(n2) and should fill in the array D defined above.

(c)    Adapt your algorithm above to return an actual LIS, not just its length. Your algorithm should run in time O(n2).

Note: Actually, there is an O(nlog(n))-time algorithm to find an LIS, which is faster than the DP solution in this exercise!

 

1. (Consider the following problem:

Let S be a set of positive integers, and let n be a non-negative integer. Find the minimal number of elements of S needed to write n as a sum of elements of S (possibly with repetitions).

For example, if S = {1,4,7} and n = 10, then we can write n = 1 + 1 + 1 + 7 and that uses four elements of S. The solution to the problem would be “4.”

Your friend has devised a divide-and-conquer algorithm for to find the minimum size. Their pseudocode is below.

def minimumElements(n, S): if n == 0:

return 0

if n < min(S):

return None candidates = [] for s in S:

cand = minimumElements( n-s, S ) if cand is not None: candidates.append( cand + 1 ) return min(candidates)

(a)    Prove that your friend’s algorithm is correct.

(b)   Argue that for S = {1,2}, your friend’s algorithm has exponential running time. (That is, running time of the form 2Ω(n)).

Turn your friend’s algorithm into a top-down dynamic programming algorithm. Your algorithm should take time O(n|S|).

(c)    Turn your friend’s algorithm into a bottom-up dynamic programming algorithm. Your algorithm should take time O(n|S|).

2. You arrive at a river where there is a population of extremely antisocial beavers. There are n sites along the river that are appropriate for beaver dams, arranged linearly.

 

Each site has a quality, which is a real number. The higher the quality, the better the dam. However, because the beavers are antisocial, no two adjacent sites can be developed into dams. You want to find a way to assign beavers to sites[1] in order to maximize the total quality of dams built: that is, if Q[i] is the quality of site i, you want to maximize

 {there is a dam at site i} · Q[i],

subject to never placing dams at adjacent sites i and i + 1.

For example, if the qualities Q were given by Q = [21,4,6,20,2,5], then the optimal solution would be for three beavers to build dams, at sites 0,3 and 5, with a total of 21 + 20 + 5 = 46 quality.

Design a dynamic programming algorithm to find the optimal locations to build dams, in the sense that it maximizes the quantity X. Your algorithm should take Q as an input, output a list of locations to build dams, and should run in time O(n) and use O(n) space.

3. Once a beaver has an n-foot by m-foot site to call their own, they have to build the most excellent dam they can on that site. Billy the Beaver wants to build a rectangular dam on his site. The n×m site is divided into n·m one-foot by one-foot squares. As above, each square has a quality, which is a real number. Notice that the qualities might be negative (that is, it costs more to build on that square than the utility gained).

Billy the Beaver’s goal is to find the rectangular dam that maximizes the total quality; he doesn’t care about the size, just that it is a rectangle. If the best quality that Billy can achieve is negative, then he will choose not to build a dam at all.

For example, if n = 3 and m = 4 and the qualities on the site were as depicted below, Billy would choose to build a 2 × 3 dam with total utility 16, which is highlighted below.

 

In the following parts, you’ll help Billy the Beaver achieve his goal in a few different settings.

(a)    Suppose that m = 1. That is, the site is a n×1 strip, and the qualities can be represented as an array B of length n.

 

Design an algorithm that takes B as input and returns two indices a,b ∈ {0,...,n − 1} so that [B[a],B[a + 1],...,B[b]] is the optimal dam site. That is, a and b are numbers so that

 

is as large as possible. Your algorithm should run in time O(n).

(b)   Now suppose that m = n. That is, the site is square. Let A be the n × n array of qualities.

 

In order to be thorough, Billy the Beaver wants to compute the score he will get for every possible dam he could build. That is, he wants to make an n×n×n×n array D so that for all x ≤ i and all y ≤ j,

                                                                                                              i        j

D[x][y][i][j] = XXA[s][t].

s=x t=y

The interpretation of the above is the total quality of the rectangle with lower-left corner (x,y) and upper-right corner (i,j). For other tuples (x,y,i,j) that don’t satisfy x ≤ i,y ≤ j, it doesn’t matter what D has in it.

Give an algorithm that takes A as input, and outputs an array D, in time O(n4).

Use your algorithm above to design an algorithm for Billy the Beaver to find the optimal rectangular dam in an n × n grid in time O(n4). Your algorithm should take A as an input and should output x,y,i,j so that the rectangle {x,...,i}×{y,...,j} corresponds to an optimal dam.

 (x,y) = (1,0),(i,j) = (2,2)

(c)    (Give an algorithm that solves part (c) (finding the optimal rectangle in an n × n grid) in time O(n3).


 
[1] Any beavers who don’t get sites at this river will go to another river and live happily ever after.