4. (a) Consider the following problem of string edit using the dynamic programming technique. The string X="abab” needs

[answerhappygod]

4 A Consider The Following Problem Of String Edit Using The Dynamic Programming Technique The String X Abab Needs 1 (67.06 KiB) Viewed 40 times

4. (a) Consider the following problem of string edit using the dynamic programming technique. The string X="abab” needs to be transformed into the string Y="babb" (i) Create the dynamic programming matrix with alphabets of string 'X' along the rows and alphabets of string 'Y' along the column entries. Calculate the min cost entries for the full matrix. Give the detailed calculation of min cost for at least two entries of the matrix. (8 marks) (ii) Calculate min cost solutions by tracing back the matrix entries from bottom right (4 marks) (b) Find solutions for a fractional Knap Sack problem which uses the criteria of maximizing the profit per unit capacity at each step, with: n=4, M=5, p=13, p2-20.p= 14, p.= 15 wi= 1, w2= 2, w3= 4, w4=3 where n is the number of objects, p is the profit, w is the weight of each object and M is the knapsack weight capacity. Show detailed calculations of how the objects are chosen in order, not just the final solution. (8 marks)