Question

4 Dynamic Programmii Consider the following problem based on the transformation of a sequence (or collection) of coloured disks. Assume that you have a very large collection of disks, each with an integer value representing the disk colour from the range [0, cl. For example, the colour mapping might be: O-red, 1-yellow, 2-blue, 3-pink,. c-black For a given sequence of coloured disks eg.,0,1,2,3,4), at each time step (or iteration) you are only allowed to perform one of three basie operations: . remove one disk from the sequence the disk you select can be any of the disks e insert one disk at any position in the sequence- the disk you select to insert can be any colour n the range 10. . replace any single coloured disk in the sequence with a different coloured disk disk can be any colour in the range o, cl the replacement e g, 0,1,2,3,4)0,1,2,3,9) Note: after multiple operations (or iterations), the length of sequence of disks may be different to the length of the starting sequence. We suggest that you represent each sequence of disks as an array (a) [6 marks Write a dynamic programming implementation for the function: TRANSFORM(A0.. 1, B[0..m ]) to calculate the minimu number of operations required to transform one given sequence of disks Al0.n- into another B(0.. 1. For example, A0,1,2,3, 40,1,3,5] requires at least two operations remove 2; replace 4 by 5. Your function must be written in clear, unambiguous pseudo code. Hint: consider approrimate string search) (b) |2 marks What is the time complexity of your algorithm? Justify your answer

i need the solution in pseudo code please.

Answer 1

Let us consider two sequences of disks(A[0 ...n-1],B[0.....m-1]):
n: Length of first sequences of disks
m: Length of second sequences of disks

//Pseudocode
Transform(A[0 ...n-1],B[0.....m-1])
{
// Create a table to store results of subproblems
int dp[n+1][m+1];
  
// Fill d[][] in bottom up manner
for (i=0 to n)
{
for (j=0; to m)
{
// If first sequence is empty, only option is to
// insert all disks of second sequence
if (i==0)
dp[i][j] = j; // Min. operations = j
  
// If second sequence is empty, only option is to
// remove all disks of second sequence
else if (j==0)
dp[i][j] = i; // Min. operations = i
  
// If last sequences are same, ignore last disk
// and recur for remaining sequence
else if (A[i-1] == B[j-1])
dp[i][j] = dp[i-1][j-1];
  
// If the last disk is different, consider all
// possibilities and find the minimum
else
dp[i][j] = 1 + min(dp[i][j-1], // Insert
dp[i-1][j], // Remove
dp[i-1][j-1]); // Replace
}
}
  
print( dp[n][m]);
}

Time complexity = O(n*m)