4 Dynamic Programming Consider the following problem based on the transformation of a sequence (or collection)...

Transcribed Image Text:

4 Dynamic Programming 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, c]. For example, the colour mapping might be: 0-red, 1-yellow, 2-blue, 3-pink, ..., c-black. For a given sequence of coloured disks e.g., (0,1,2,3,4), at each time step (or iteration) you are only allowed to perform one of three basic operations: • remove one disk from the sequence - the disk you select can be any of the disks eg., (0,1,2,3,4) (0,1,3,4) • insert one disk at any position in the sequence - the disk you select to insert can be any colour in the range [0, c] e.g., (0,1,2,3,4)→ (0,1,9,2,3,4) • replace any single coloured disk in the sequence with a different coloured disk-the replacement disk can be any colour in the range [0, c 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(A[0..n-1], B[0..m-1]) to calculate the minimum number of operations required to transform one given sequence of disks A[0..n-1] into another B[0..m-1]. For example, A[0, 1, 2, 3, 4] B[0, 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 approximate string search) (b) [2 marks] What is the time complexity of your algorithm? Justify your answer. 4 Dynamic Programming 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, c]. For example, the colour mapping might be: 0-red, 1-yellow, 2-blue, 3-pink, ..., c-black. For a given sequence of coloured disks e.g., (0,1,2,3,4), at each time step (or iteration) you are only allowed to perform one of three basic operations: • remove one disk from the sequence - the disk you select can be any of the disks eg., (0,1,2,3,4) (0,1,3,4) • insert one disk at any position in the sequence - the disk you select to insert can be any colour in the range [0, c] e.g., (0,1,2,3,4)→ (0,1,9,2,3,4) • replace any single coloured disk in the sequence with a different coloured disk-the replacement disk can be any colour in the range [0, c 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(A[0..n-1], B[0..m-1]) to calculate the minimum number of operations required to transform one given sequence of disks A[0..n-1] into another B[0..m-1]. For example, A[0, 1, 2, 3, 4] B[0, 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 approximate string search) (b) [2 marks] What is the time complexity of your algorithm? Justify your answer.

Answer rating: 100% (QA)

a Algorithm for TRANSFORM Function TRANSFORMA0n1 B0m1 1 Create a 2dimensional array C0n 0... View the full answer