There is a river which flows horizontally through a country . There are N cities on the north side of the reiver and M cities on the south side of the river . The X coordinates of the N cities on the north side of the river are n1, n2 ....n N and the N coordinates of the M cities on the south side of the river are s1, s2...s M.

Assume that we can apply build bridges between cities with the same number from north and south sides. In this problem you have to determine the maximum number of bridges we can build without any bridges crossing with each other . Note that both n1 through n N and s1 through sM are not sorted

a) Define the problem in terms of subproblems. Use that definition prove that this problem exhibits optimal substructure

b)Describe a dynamic programming algorithm to solve the problem.

c) What is the time compexity of your algorithm ?

d) Illustrate your algorithm for the following instance

n= (3,7,9,2,4,1,5,6 ) and s= (7,3,2,9,5,4,6)