CSC$413/513$

Assignment #$6$: Implementation of the Longest Common Subsequence $($LCS$)$ Algorithm

Objective:

This assignment aims to implement dynamic programming algorithms for finding the Longest Common Subsequence $($LCS$)$ of two sequences $($and compare its performance with a brute force approach$).$ By completing this assignment, students will deepen their understanding of algorithmic techniques and their efficiency in solving the LCS problem.

Assignment $(70$ points$)$:

Write a C$++$ program to implement the LCS algorithm covered in class for finding the Longest Common Subsequence $($LCS$)$ of two sequences. Provide comprehensive comments and explanations within your code to elucidate the logic and implementation of the dynamic programming approach. Note that LCS is different from a common substring. Test your program with the following two cases to verify the correctness of your implementation:

Test Case $1$:

Given two sequences $x$ and $Y$ :

$x=(A,B,C,B,D,A,B$:$)$ and $Y=(B,D,C,A,B,A)$

Test Case $2$:

Given two gene sequences $S1$ and $S2$ :

$S_1=$ ACCGGTCGAGTGCGCGGAAGCCGGCCGAA

$S_2=$ GTCGTTCGGAATGCCGTTGCTCTGTAAA

Write a report comprising:

A cover page $($course information, assignment details, your name$).$

Table of contents.

Brief description of the LCS algorithm.

Description of your implementation.

Results of your testing, including sample inputs and corresponding outputs. Include screenshots showing program execution, inputs, and outputs.

Discussion of your implementation and results.

Bonus Question $($Extra $30$ points$)$

Design a brute force algorithm to find the Longest Common Subsequence $($LCS$)$ of two sequences.

Implement the brute force algorithm in $C++.$

Include the following in the report as a separate section:

Detail description of your brutal force algorithm.

Compare the results obtained from the brute force algorithm with those obtained from the dynamic programming LCS algorithm using the same two test cases.

Compare the running time of the two implementations using two very long sequences generated by you.

Analyze the time complexity of the brute force solution and compare it with the dynamic programming approach.

Discuss the advantages and disadvantages of each algorithm in terms of efficiency and applicability to different scenarios.

Conclusions$/$Summary: Summarize whether yofr brute force algorithm yields accurate results and its performance compared with the dynamic programming LCS algorithm.

Submission:

Please submit your $C++$ code for the dynamic programming LCS algorithm along with the report. If you have completed the bonus question, ensure that you submit the $C++$ code for the bonus algorithm as well and your report should include the bonus section with the required contents.

Note:

Adhere to good coding practices, including proper indentation, meaningful variable names, and clear commenting in your $C++$ programs.

There is no page limit for your report; focus on presenting the content effectively. Shorter reports are preferred if they are well$-$organized.