Design and implement algorithms to solve the longest common subsequence problem (chapter 15.4).

S1 = ACCGGTCGACTGCGCGGAAGCCGGCCGAA

S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA

S3 = ATTGCATTGCATGGGCGCGATGCATTTGGTTAATTCCTCG

S4 = CTTGCTTAAATGTGCA

Compare each of the provided strings to each other and to your test cases. Compare by pairs only, finding the LCS of the pair. Gaps in matching the substring are allowed.

Here is a related YouTube video you might interesting "A Dynamic Programming Algorithm - Sequence Alignment " - By Tim Roughgarden https://youtu.be/xccdfMM6l7c. Roughgarden has other useful videos as well. Count individual comparisons to use as a basis for cost-efficiency in terms of the string lengths.

If you want to try timing, please do it in addition to, not instead of, counting comparisons. A file with required input is provided. The required input is used to demonstrate correctness. You should supplement this with your own cases that demonstrate correctness in various standard error situations, To demonstrate the asymptotic cost you will need to create, additional input sets with larger strings. You need to collect enough data to have a meaningful comparison of the theoretical efficiency to the observed efficiency. The analysis must include a table and a graph of the asymptotic costs that you observed.

PLEASE INCLUDE THE TIME TAKEN TO COMPLETE THE COMPARISONS

DO NOT HARD CODE THE INPUT DATA

WRITE THE OUTPUT TO A FILE