# Algorithms - Programming Assignment

• Status: Closed
• Prize: \$50
• Winner: edulov

## Contest Brief

Hi,
I need solution for this assignment in java code as soon as possible.

1 Longest Common Substring
Consider the Longest Common Substring (LCS) problem studied in chapter 4.

1. Recall the recursive formula for the optimal subproblem of the LCS (just the length, not the substring).
2. Write a code that finds the LCS between two arbitrary strings by using dynamic programming
3. Write a code that finds the LCS between two arbitrary strings by using recursive functions
4. Consider the following two strings: str1 = ”GHCLPPOEWMOHGFMDSOxzn” and Str2
= ”ARSDCSFOMOLKMIUOONP”. Report and compare the numbers of instructions necessary for finding the LCS by the previous two programs.
5. Use the concept of memoization for the second code (with recursive functions) and report the new number of executed instructions.
6. Comment on the three results.
7. Consider now the two strings X=“TCSFOGMLKM” and Y=“CTPPOMEWMH”. Use the idea of arrows of the LCS-LENGTH algorithm in page 394 of textbook, to draw a table similar to the one of page 395. Use the table to find all the LCS substrings of X and Y and show your solution on the table.

2 Longest palindrome subsequence
A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are: all strings of length 1, “civic”, “racecar”, and “aibohphobia”.
1. Explain an algorithm that uses LCS algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac.

2. Bonus Question: What is the palindrome of the DNA sequence “TAACATTCT GACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTGTCTGA
TAGCAGCTTCTGAACTGGTTACCTGCCGTGAGTAAATTAAAATTTTATTGA CTTAGGTCACTAAATACTTTCCAATATAGGCATAGCGAATCA”?

3 Assignment Requirements
The assignment should be submitted by taking in consideration the following points:
• For each question, provide first the question text, then the code if any with its brief description, then the answer.

I can pay up to \$50
Thank you

Winner

## Employer Feedback

“Thank you I would like to work with you again ”

Helena505, Saudi Arabia.

No messages yet.

## How to get started with contests

• Post Your Contest Quick and easy

• Get Tons of Entries From around the world