COMP3711 - Design and Analysis of Algorithms - Assignment 4 - Solved

Problem 1: [25pts] Longest Common Subsequence of Three Sequences.

In class you learned a DP algorithm for finding the longest common subsequence of two sequences. In this problem you need to extend that algorithm to three sequences.

More specifically, let

                                                        W = (w1,...,wp),             X = (x1,...,xm),             Y = (y1,...,yn)

                                be three given sequences.          Z = (z1,...,zq) is a common subsequence of

W,X,Y if zt = wit = xjt = ykt for all t = 1,...,q where i1 < i2 ··· < iq, j1 < j2 < ··· < jq, k1 < k2 < ··· < kq. (1)

The problem is to find the length of the longest common subsequence of the three sequences, i.e., the largest possible such q.

As an example, an LCS of W = gahbczha, X = zargbrca and Y =

azbrcgar, is Z = abca,

Define c[i,j,k] to be the length of the longest common subsequence of W[1...i], X[1...j] and Y [1...k].

Your goal is to calculate c[p,m,n].

(a)     Write down a recurrence relation for c[i,j,k]. It should be written in the form



                                                                                                 ???????     if ??????????????



                                                                    c[i,j,k] =         ???????     if ??????????????

                                                                                         ...              ...

Your recurrence should include the initial conditions.

(b)    Derive the correctness of the recurrence relation for part (a).

(c)     Give documented pseudocode for an algorithm for calculating c[p,m,n], based on your recurrence relation from (a).

(d)    Analyze the running time of your algorithm. For full marks, your algorithm should run in O(pmn) time.

Problem 2 [25 pts] Prize Collecting Walks on a Grid
The input to this problem is an m × n grid. The top left entry is (1,1) the bottom right entry is (m,n). Entry (i,j) in the grid contains a prize or penalty with known worth P(i,j) (the input).

A walk starts at (1,1) and terminates at (m,n). At each step you can either move one unit to the right or one unit down or one unit to the right and one unit down. That is, from (i,j) you may move to either (i,j + 1), (i + 1,j) or (i + 1,j + 1) (if you are on the boundary and only one such neighbor exists, you must move to that existing neighbor).

When you land on (k,r) you collect or pay money. How much you collect/pay depends on both P(k,r) and how you got to (k,r).

If you move from (i,j) to (i + 1,j) or (i,j + 1) you will earn, respectively,

 + 1). But, if you move to (i + 1,j + 1), you will earn

The Value of a walk is the sum of all the prizes/penalties that you have collected/paid. Your goal is find the largest possible value walk. It is not necessary to find the walk itself; just the value.

As an example, consider the grid and walk shown below

 

This walk has value 1 +  2) + 10 + 18 + 10 = 55 which is a max value walk.

Design an O(mn) time dynamic programming algorithm for finding a maximumvalue walk.

(a)     Give the recurrence upon which your DP algorithm is based. Before giving the recurrence, define (using english and math symbols) the meaning of each entry.

Don’t forget to completely specify the initial conditions of the recurrence relation.

(b)    Explain how, after filling in your table, you can use the information in your table to solve the problem.

Note: This is meant to have a one line answer. Is the solution a particular table entry? If so, which entry? Or is it a function, e.g., the maximum, of a set of table entries?

(c)     Prove the correctness of the recurrence relation from part (a).

(d)    Give documented psuedocode for your algorithm. Your code only needs to find the value of a maximum-value walk, not the actual walk itself.

(e)     Explain why your algorithm runs in O(nm) time.

Added November 12, 2021. Although this was illustrated in the example, the original definition of the problem did not make it clear that the value of the path always includes P(1,1).

To make this consistent you should assume that the walk really always starts at (imaginary) vertex (1,0) and the first step is always a move from (1,0) to (1,1). That will make it clear that the value P(1,1) is always included in the value of the path.


Problem 3 [20 pts] Depth and Breadth First Search
In this problem you will have to describe the depth and breadth first search trees calculated for particular graphs. Let graph Gn be the n × n grid containing the n2 points (i,j), i = 0,...,n − 1, j = 0,...,n − 1. Figure (A) illustrates G6. Each point is connected to four neighbors: the one to its right, the one above it, the one to its left, and the one below it. Note that some points only have two or three neighbors, e.g., the four corner points only have 2 neighbors and that the edge points (aside from the corners) each have three neighbors. The adjacency list representation used is

(i,j) :→ (i + 1,j) → (i,j + 1) → (i − 1,j) → (i,j − 1).

For example, the adjacency list representation for (1,1) in G6 is

(1,1) :→ (2,1) → (1,2) → (0,1) → (1,0).

                                                                                             (0,5)                                                                                                                                                     (5,5)                                            (0,5)                                                                                                                                                     (5,5)

                                                                (0,0)                                                                                                                                                     (5,0)                                            (0,0)                                                                                                                                                     (5,0)

                     (0,0)                                                                                                                                                     (5,0)                                                                             (1,0)                                                                                                                                                                                                            (1,0)

                                                    (A)                                           (B)                                                (C)
Some nodes will only have two or three neighbors; their adjacency lists should be adjusted appropriately. For example

(0,0) :→ (1,0) → (0,1)         and      (i,0) :→ (i + 1,0) → (i,1) → (i − 1,0) for i = 1,...,n − 2.

In what follows Describe the tree means (i) list the edges in the tree and (ii) sketch a diagram that illustrates how the tree looks.

(a)                Describe the tree produced by Depth First Search run on Gn, for all n ≥ 6, starting at root s = (1,0). Figure (B) illustrates the tree produced for G6.

(b)               Describe the tree produced by Breadth First Search run on Gn, for all n ≥ 6, starting at root s = (1,0). Figure (C) illustrates the tree produced for G6.

Hint: experiment by drawing the BFS and DFS trees for n = 5,6,7,8. You should see a pattern.

Problem 4 [20 pts] Implicit Graphs
Many graph problems are not actually presented as graph problems. Graphs are only introduced as part of the solution technique. Also, the graphs are often not given explicitly but are only implicitly defined.

Consider the following “3-jug” problem. You are given 3 jugs of known capacities. The first jug holds 8 liters, the second 5 liters, the third 3 liters.

•     The 8-liter jug is filled with water; the other two are empty.

•     You can pour water from any jug to any other jug, stopping when the pouring jug is empty or the poured into jug is full (whichever comes first)

•     You have no other way of measuring water

The problem is usually given as “Is there any sequence of water-pouring that would terminate with the water equally divided so that there are 4 liters each in the first and second jug?”.

You will solve this and other problems using BFS and DFS.

Consider the directed graph G8 = (V,E) defined as follows

•     Vertices represent possible configurations of 8 liters in the bottles (all numbers are nonnegative integers)

 .

•     Let v1 = (a1,b1,c1) and v2 = (a2,b2,c2) where v1 6= v2 and v1,v2 ∈ V. Edge v1 → v2 exists if it is possible to legally get from configuration v1 to configuration v2 by pouring water from one jug to the other, i.e., one of the following 6 moves occurs:

(i)        (a2,b2,c2) = (a1 − p,b1 + p,c1) where p = min(a1,5 − b1)

(ii)      (a2,b2,c2) = (a1 − p,b1,c1 + p) where p = min(a1,3 − c1)

(iii)    (a2,b2,c2) = (a1 + p,b1 − p,c1) where p = min(b1,8 − a1)

(iv)    (a2,b2,c2) = (a1,b1 − p,c1 + p) where p = min(b1,3 − c1)

(v)       (a2,b2,c2) = (a1 + p,b1,c1 − p) where p = min(c1,8 − a1)

(vi)    (a2,b2,c2) = (a1,b1 + p,c1 − p) where p = min(c1,5 − b1)

•     The adjacency list of v should be ordered as (i), (ii), (iii), (iv), (v), (vi), only including the edges that occur. For example, the adjacency list of v = (2,4,2) is

(2,4,2) : (1,5,2), (1,4,3), (6,0,2), (2,3,3), (4,4,0), (2,5,1) while the adjacency list of v = (1,5,2) is

(1,5,2) : (0,5,3), (6,0,2), (1,4,3), (3,5,0).

Recall that “v0 is reachable from v” if there is a path from v to v0 in G8.

Let v0 = (8,0,0) be the vertex corresponding to the configuration that has all of the water in one jug,

Now answer all of the following questions:

(A)      Draw the BFS tree that results from running BFS starting at v0.

Note that this tree is rooted at v0.

You only need to draw the tree of all items that are reachable from v0. This might or might not be the entire graph.

(B)      Draw the DFS tree that results from running DFS starting at v0.

Again, note that this tree is rooted at v0 and you only need to draw the tree of all items that are reachable from v0. This might or might not be the entire graph.

(C)      Start with 8 liters of water in the jug of capacity 8.

Is there any sequence of water-pouring that would terminate with 4 liters each in the first and second jug?

If there is such a way, describe a method to achieve this that uses the least number of pouring steps.

(D)     Justify the correctness of your answer to part (C) using the answers to parts (A) and/or (B).

(E)      Start with 8 liters of water in the jug of capacity 8.

Is there any sequence of water-pouring that would terminate with 6 liters in the first jug and 1 liter each in the second and third jugs.

If there is such a way, describe a method that uses the least number of pouring steps.

(F)      Justify the correctness of your answer to part (E) using the answers to parts (A) and/or (B).

(G)      Prove or disprove the following statement: For all v ∈ V − {v0}, if v is reachable from v0 then v0 is reachable from v.

(H)     Prove or disprove the following statement: For all v ∈ V − {v0},

if v0 is reachable from v then v is reachable from v0

Note: (C) and (E) are standard puzzle questions. For (D) and (F) you must either prove that your method uses the minimal number of pours or explain how you know that no method exists. (G) and (H) are to help you understand if the problem is “reversible” and how that translates into graph language.

Problem 5 [10 points] Optimal Binary Search Trees
Consider the following input to the Optimal Binary Search Tree problem (it is presented in the same format as in the example powerpoint file posted on the lecture page):

i
1
2
3
4
5
6
7
8
ai
A
B
C
D
E
F
G
H
f(ai)
5
15
5
5
10
10
20
5
a)   Fill in the two tables below. As in the example powerpoint only theentries with i ≤ j need to be filled in. We have started you off by filling in the [i,i] entries.

i/j
1
2
3
4
5
6
7
8
 
i/j
1
2
3
4
5
6
7
8
1
5
 
 
 
 
 
 
 
 
1
1
 
 
 
 
 
 
 
2
 
15
 
 
 
 
 
 
2
 
2
 
 
 
 
 
 
3
 
 
5
 
 
 
 
 
3
 
 
3
 
 
 
 
 
4
 
 
 
5
 
 
 
 
4
 
 
 
4
 
 
 
 
5
 
 
 
 
10
 
 
 
5
 
 
 
 
5
 
 
 
6
 
 
 
 
 
10
 
 
6
 
 
 
 
 
6
 
 
7
 
 
 
 
 
 
20
 
7
 
 
 
 
 
 
7
 
8
 
 
 
 
 
 
 
5
8
 
 
 
 
 
 
 
8
                        Table 1: Left matrix is e[i,j].                                           Right matrix is root[i,j].

b)   Draw the optimal Binary Search Tree (with 8 nodes) and give its cost.