代写EE205留学生、代做Dynamic Programming、代做C++编程语言、C/C++代写

日期：2019-06-09 10:56

EE205 Project 2

Assign 2019-05-20    Due 2019-06-18

Longest Palindromic Subsequence

Given a sequence, find the length of the longest palindromic subsequence in it.

if the given sequence is “BBABCBCAB”, then the output should be 7 as “BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.

The task is to find the optimal substructure and solve the problem using dynamic programming.

Submit:

1.Files to submit: EE205_studentID_name(CN).h and EE205_studentID_name(CN).cpp

2.The following class definition is included in your header file. You should complete the methods of the class in the .cpp file. Some comments could be added to be read easily by TA

// A Dynamic Programming based C++ program for LPS problem

// Returns the length of the longest palindromic subsequence

#include<string.h>

class LongestPalindromeSubsequence{

private:

   char *str;//string

   int n;//the length of string

   int **L;//a table to store results of subproblems

public:

   // constructor with argument, "str" and "n" are obtained

   LongestPalindromeSubsequence(char *str);

   int max (int x, int y);

   //create table L dynamically and initialize all the elements to be zero

   void create_L();

   // get the length of the longest palindrome subsequences

   int lps();

   void print_str();

   void print_L();

};

3.The descriptions of the class LongestPalindromeSubsequence are as follows:

a)str is the string, and n is the length of the string.

b)L is the table to store the result of subproblems, which should be n*n.

c)LongestPalindromeSubsequence(char *str) is the constructor of the class.

d)The method create_L() is to create the table of “L” dynamically and initialize all the elements of the table is to be zero.

e)The method int lps() is to get the length of the longest palindrome subsequence in the string str.

4.Score

a)You should use LongestPalindromeSubsequence(char *str), the constructor with arguments, explicitly to construct an instance. (10% )

b)The table L should be created for n*n dynamically and initialized by the method void create_L() .(20%)

CAUTION: If the matrix is a static 2-D array, the score will be marked 0 !

c)Implement the method int lps() to get the result correctly. (50%)

d)The method void print_L() is to print out the table L correctly. (20%)

5.Submit by email:

a)Email subject : EE205_studentID_studentName(CN).

b)Send email to TA after attaching your .h and .cpp files.

c)TA’s (Zhang Chenxi) email address: chenxi19990406@163.com

6.Due date: Due 2018-06-18

a)No acceptance after 5 days.

b)10% penalty per day up to 5 days.

c)One lower course grade for no submission.

7.The following file can be used to test your code.

1.int main()

2.{

3.    char s1[] = "BBABCBCAB";

4.    char s2[] = "BBABCBBACBBCAB";

5.    

6.    LongestPalindromeSubsequence a(s1);

7.    a.print_str();

8.    cout << "The length of the LPS is" << a.lps() <<endl;

9.    a.print_L();

10.    

11.    cout << endl << endl;

12.    LongestPalindromeSubsequence b(s2);

13.    b.print_str();

14.    cout << "The length of the LPS is" << b.lps() <<endl;

15.    b.print_L();

16.    

17.    return 0;

18.}