Question $5.$

$($a$)$ Find the longest common subsequence between the two sequences CGTA and CCTGA using dynamic programming. You only need to write down the final contents of the dynamic programming table, mark the traceback path on the table, and write down the longest common subsequence itself.

$[8$ marks$]$

$($b$)$ Given an array $A[1..n]$ of $n$ numbers, a certain optimisation problem about maximising the total of some values chosen from the array can be solved by the following recursive formulation. $($The exact nature of the optimisation problem does not concern us here.$)$ Let $F(i)$ be the optimal value for the subproblem consisting of the first i numbers of $A,$ i$.$e$.A[1..i].$ Then

$)(1)(2)(4$

If some of these terms result in invalid parameters inside $)($e$.$g$.F(-1)),$ that term is disregarded. Furthermore $F(0)=0($for an empty array$).$

Write down the pseudocode of an efficient algorithm that computes $F(n).$ State its time and space complexity.

$[7$ marks$]$