Ex 7

Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam - 603 110
(An Autonomous Institution, Affiliated to Anna University, Chennai)
UCS2403: DESIGN & ANALYSIS OF ALGORITHMS
Assignment 7
1. Given two sequences X = ⟨x1,...,xm⟩ and Y = ⟨y1,...,yn⟩, the longest common sub-sequence problem
(LCS) seeks to find a maximum length common sub-sequence of X and Y .
For example, if X = ⟨A,B,C,B,D,A,B⟩ and Y = ⟨B,D,C,A,B,A⟩, then the sequences ⟨B,C,B,A⟩ and
⟨B,D,A,B⟩ are the longest common sub-sequences, since X and Y have no common sub-sequence
of length 5 or greater.
(a) Obtain a recursive formula for the LCS problem.

(b) Design a dynamic programming algorithm to solve the LCS problemusing the recursive
formula in Q 1(a). Write the Python code to implement the same.
(c) Populate the table using bottom-up approach, starting from the basecase(s), for the below
example: X = ⟨A,B,A,A,B,A⟩ and Y = ⟨B,A,B,B,A,B⟩. Find the answer using the data populated in
the table.
(d) Compare the output/answers obtained in Q 1(b) and Q 1(c) for thegiven example.
2. In Domino Solitaire, you have a grid with two rows and many columns.Each square in the grid
contains an integer. You are given a supply of rectangular 2 × 1 tiles, each of which exactly covers
two adjacent squares of the grid. You have to place tiles to cover all the squares in the grid such
that each tile covers two squares and no pair of tiles overlap. The score for a tile is the difference
between the bigger and the smaller number that are covered by the tile. The aim of the game is to
maximize the sum of the scores of all the tiles. Here is an example of a grid, along with two different
tilings and their scores.
The score for Tiling 1 is 12 = (9 − 8) + (6 − 2) + (7 − 1) + (3 − 2) while the score for Tiling 2 is 6 = (8 −

6) + (9 − 7) + (3 − 2) + (2 − 1). There are other tilings possible for this grid, but you can verify that
Tiling 1 has the maximum score among all tilings. Your task is to read the grid of numbers and
compute the maximum score that can be achieved by any tiling of the grid.
1|Page
Ex no:7 UCS2403: DESIGN & ANALYSIS OF ALGORITHMS Name: Micheal Berdinanth M
24-04-2024 Assignment - 7 Regno:3122 22 5001 071
Aim:
To learn different varieties of dynamic programming problems.
Q.No 1 : Algorithm
2|Page
3|Page
Python Code
def dp_lcs(str1, str2, m, n, dp):
if m == 0 or n == 0:
return 0
if dp[m][n] != -1:
return dp[m][n]
if str1[m-1] == str2[n-1]:
dp[m][n] = 1 + dp_lcs(str1, str2, m-1, n-1, dp)
else:
dp[m][n] = max(dp_lcs(str1, str2, m, n-1, dp), dp_lcs(str1, str2, m-1,
n, dp))
return dp[m][n]
def print_lcs(str1, str2, m, n, dp):

if m == 0 or n == 0:
return
if str1[m - 1] == str2[n - 1]:

print_lcs(str1, str2, m - 1, n - 1, dp)
print(str1[m - 1], end=" ")
else:
if dp[m][n - 1] >= dp[m - 1][n

print_lcs(str1, str2, m, n - 1, dp)
else:
print_lcs(str1, str2, m - 1, n, dp)
def bottumup_lcs(X, Y, m, n):
L = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
4|Page
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
str1 = "ABCBDAB"
str2 = "BDCABA"
m = len(str1)
n = len(str2)
dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
lcs_length = dp_lcs(str1, str2, m, n, dp)
print("Length of LCS By DP:", lcs_length)
lcs_length = lcs(str1, str2, m, n)
print("Length of LCS By Bottom Up:", lcs_length)

print("LCS sequence:", end=" ")
print_lcs(str1, str2, m, n, dp)
OUTPUT
5|Page
Q.No 2 : Algorithm
Python Code
#domino solitaire problem
no_of_cols=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
prev_state=0
final=abs(arr1[0]-arr2[0])
for i in range(1,no_of_cols):
vertical=final+abs(arr1[i]-arr2[i])
horizontal=prev_state+abs(arr1[i]-arr1[i-1])+abs(arr2[i]-arr2[i-1])
prev_state=final
final=max(vertical,horizontal)
print("Score:",final)
6|Page
Output
Learning Outcomes
Through this exercise,

→I learnt Memoization.
→I learnt bottom up approach to built the solution.
→I learnt difference between recursion and bottom up

approach.
7|Page

Ex 7

Uploaded by

Copyright:

Available Formats

Ex 7

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ex 7

Uploaded by

Copyright:

Available Formats

Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam - 603 110

(An Autonomous Institution, Affiliated to Anna University, Chennai)

UCS2403: DESIGN & ANALYSIS OF ALGORITHMS

(a) Obtain a recursive formula for the LCS problem.

The score for Tiling 1 is 12 = (9 − 8) + (6 − 2) + (7 − 1) + (3 − 2) while the score for Tiling 2 is 6 = (8 −

24-04-2024 Assignment - 7 Regno:3122 22 5001 071

To learn different varieties of dynamic programming problems.

def dp_lcs(str1, str2, m, n, dp):

def print_lcs(str1, str2, m, n, dp):

if str1[m - 1] == str2[n - 1]:

if dp[m][n - 1] >= dp[m - 1][n

def bottumup_lcs(X, Y, m, n):

L = [[None]*(n+1) for i in range(m+1)]

lcs_length = dp_lcs(str1, str2, m, n, dp)

print("Length of LCS By DP:", lcs_length)

lcs_length = lcs(str1, str2, m, n)

print("Length of LCS By Bottom Up:", lcs_length)

Through this exercise,

→I learnt bottom up approach to built the solution.

→I learnt difference between recursion and bottom up

You might also like