1. (20 points) Dynamic Programming. Consider a map of the Brazilian rainforest w
ID: 3765946 • Letter: 1
Question
1. (20 points) Dynamic Programming. Consider a map of the Brazilian rainforest with the Amazon River passing horizontally through the center. Along the southern bank of the river are villages. In these villages are m different Indian tribes, which do not get along. Let Tbe the set of size rm that contains all of these tribes, and let s be a function that maps each southern village to the Indian tribe living there. On the northern bank are m other villages, which are inhabited by the same m tribes. The members of one tribe, however, may not be directly across the river from other members of their tribe (i.e. the Nukak may inhabit the first village on the southern bank, but the other Nukak may be in the third village on the northern bank and directly across from them on the northern bank may be the Akuntsu). Let nbe a function that maps each northern village to only one tribe in the set as possible to villages on the northern bank with rope bridges, but the You want to connect as many villages on the southern bank bridges can only connect members of the same tribe and can't cross each other. How would you determine the maximum number of tribes that can be reunited? Hint: Can you translate this problem into a Longest Common Subsequence problem?Explanation / Answer
let the tribes be denoted by 1,2,3....,n.
let S be an array of size n containing a permutaion of tribes denoting the tribes on south of the river.
similarly let T be an array of size n containing a permutaion of tribes denoting the tribes on north of the river.
now we have to find maximum number of bridges that can be built between these two arrays such that no two bridges cross with each other.
let a1,a2,a3,...ak be the tribes for which maximum number of bridges can be constructed such that no two cross with each other and k be the maximum number(answer to the problem).
observation 1:
a1,a2,a3,...ak occur in same order in both the arrays.
proof: It can be prooved by contradiction.
suppose b1,b2,b3,..bk is the order of ai's in S.
c1,c2,c3,...ck is the order of ai's in T.
Iterate from 1 to k and let j be the index where there is a mismatch.(Till then bi=ci).
bj!=cj
There exists bp and cq such that bj=c1 and cj=bp
which result in crossed edges.(CONTRADICTION).
Therefore a1,a2,a3,...ak occur in same order in both the arrays.
Claim: solution to the problem is nothing but the length of longest common subsequence of S and T.
let Longest common subsequence of S and T be d1,d2,....dl.
We know this sequence occur in the same order in S and T.
So, connect d1 in S and d1 in T , d2 in S and d2 in T ..............
so this is a valid solution.
Now we have to prove this is maximum.
proof: suppose this is not maximum then there exist atleast one dm that is not present in longest common sunsequence such that dm is in S and T and bridge across them does not cross any other bridge.
Then we can see that dm can also be included in d1,d2,d3....dl. Then this sequence is longer than the losngest common subsequence.(Contradiction).
Therefore this is the maximum.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.