Objective: Students will apply concepts of dynamic programming and the LCS problem. Assignment Description: Your friend...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Objective: Students will apply concepts of dynamic programming and the LCS problem. Assignment Description: Your friend has intercepted a message that is riddled with random characters. Your friend tries really hard to decipher the message ("qwadhyuitrrejghfhgkllqwrto"), but couldn't. A couple of minutes later your friend receives another message ("mpoihselyzmxcvldfiuoydmnbv") riddled with random characters. Something interesting your friend noticed is that it seems to have the same number of characters. Your friend tells you about this and you are curious too. You have just listened to a lecture by Dr. Steinberg about finding longest common sequences and immediately practice on this long message to study for giggles. After completing by hand the steps of finding the longest common sequence, you get an actual word ("hello") as the longest common sequence and realize the secret of this message is through the longest common subsequence. The next day you tell your friend what you discovered. Coincidentally your friend receives another two message with the same length of characters. However, this one is a long sequence and can be time consuming to do by hand. In this assignment you are going to reveal the secret message. In this assignment, you have intercepted the document and are going to decipher the message. In order to do this, you will need to apply the Longest Common Subsequence Algorithm discussed in class. You must apply the dynamic programming solution. Using another variation will result in losing points. For this assignment, you must follow these requirements. 1. Create a class called LCS. In this class, you will implement the dynamic programming algorithm. 2. The class constructor for LCS takes two string objects. 3. In the runner file, you will notice the method "lcsDynamic Sol" is invoked. This is the method that will invoke the dynamic programming solution. Make sure the method name matches as the runner file in your implementation! Changing names will cause the runner file not to run or even compile which will result in a low score on the assignment! 4. In the runner file, you will notice the method "getLCS" is invoked. This is the method that will access the subsequence computed by the dynamic programming solution. This is the Print-LCS algorithm we discussed in class. Make sure the method name matches as the runner file in your implementation! Changing names will cause the runner file not to run or even compile which will result in a low score on the assignment! 5. Make all methods public and class attribute private. It's good practice! 6. You may create additional helper methods and attributes if needed as long as they are implemented and called in your solution file and NOT called from the runner file. Adding extra methods to call in the runner file will not match to what the graders will use evaluate your code. This will result in a low score with no change to be applied! 7. Your code must run within 2 seconds on Eustis. If it runs longer than 2 seconds, an automatic score of 0 will be given for the assignment overall. A runner file (LCSRunner.java) has been provided for you to show you how the methods are called along with 4 test cases. The text file is also provided for you that you will need to decipher using the LCS algorithm. The text file itself must be in the same directory as the runner file. The number of characters to be read from the file on each line will have no more than 1000 characters. What to submit: Submit a file called LCS.java to webcourses. You are not required to submit the runner file as that will be provided for the graders to test your code. Please make sure the runner file provided works for your code. Any name changes may cause your program not to work when graded, which will result in a lower score on the assignment and would not be changed. Important Note for running Eustis: Many of you are probably using IDEs like Netbeans and Eclipse to build your Java Solutions. Please note that some of these IDEs will automatically place your Java file in some sort of package. Please make sure your Java file is not defined in some package as this can result package private errors. Any such error that occurs during the grading will not be fixed and points will be deducted as such in accordance with the respective categories in the rubric. Also, DO NOT create a main method in your solution file!! This will result in your code not running properly with the runner file which will result in points being deducted from the respective categories. Objective: Students will apply concepts of dynamic programming and the LCS problem. Assignment Description: Your friend has intercepted a message that is riddled with random characters. Your friend tries really hard to decipher the message ("qwadhyuitrrejghfhgkllqwrto"), but couldn't. A couple of minutes later your friend receives another message ("mpoihselyzmxcvldfiuoydmnbv") riddled with random characters. Something interesting your friend noticed is that it seems to have the same number of characters. Your friend tells you about this and you are curious too. You have just listened to a lecture by Dr. Steinberg about finding longest common sequences and immediately practice on this long message to study for giggles. After completing by hand the steps of finding the longest common sequence, you get an actual word ("hello") as the longest common sequence and realize the secret of this message is through the longest common subsequence. The next day you tell your friend what you discovered. Coincidentally your friend receives another two message with the same length of characters. However, this one is a long sequence and can be time consuming to do by hand. In this assignment you are going to reveal the secret message. In this assignment, you have intercepted the document and are going to decipher the message. In order to do this, you will need to apply the Longest Common Subsequence Algorithm discussed in class. You must apply the dynamic programming solution. Using another variation will result in losing points. For this assignment, you must follow these requirements. 1. Create a class called LCS. In this class, you will implement the dynamic programming algorithm. 2. The class constructor for LCS takes two string objects. 3. In the runner file, you will notice the method "lcsDynamic Sol" is invoked. This is the method that will invoke the dynamic programming solution. Make sure the method name matches as the runner file in your implementation! Changing names will cause the runner file not to run or even compile which will result in a low score on the assignment! 4. In the runner file, you will notice the method "getLCS" is invoked. This is the method that will access the subsequence computed by the dynamic programming solution. This is the Print-LCS algorithm we discussed in class. Make sure the method name matches as the runner file in your implementation! Changing names will cause the runner file not to run or even compile which will result in a low score on the assignment! 5. Make all methods public and class attribute private. It's good practice! 6. You may create additional helper methods and attributes if needed as long as they are implemented and called in your solution file and NOT called from the runner file. Adding extra methods to call in the runner file will not match to what the graders will use evaluate your code. This will result in a low score with no change to be applied! 7. Your code must run within 2 seconds on Eustis. If it runs longer than 2 seconds, an automatic score of 0 will be given for the assignment overall. A runner file (LCSRunner.java) has been provided for you to show you how the methods are called along with 4 test cases. The text file is also provided for you that you will need to decipher using the LCS algorithm. The text file itself must be in the same directory as the runner file. The number of characters to be read from the file on each line will have no more than 1000 characters. What to submit: Submit a file called LCS.java to webcourses. You are not required to submit the runner file as that will be provided for the graders to test your code. Please make sure the runner file provided works for your code. Any name changes may cause your program not to work when graded, which will result in a lower score on the assignment and would not be changed. Important Note for running Eustis: Many of you are probably using IDEs like Netbeans and Eclipse to build your Java Solutions. Please note that some of these IDEs will automatically place your Java file in some sort of package. Please make sure your Java file is not defined in some package as this can result package private errors. Any such error that occurs during the grading will not be fixed and points will be deducted as such in accordance with the respective categories in the rubric. Also, DO NOT create a main method in your solution file!! This will result in your code not running properly with the runner file which will result in points being deducted from the respective categories.
Expert Answer:
Answer rating: 100% (QA)
Below is an example implementation of the LCS class in Java adhering to the provided assignment requ... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
Show that every continuous function f : D D on a domain D has a least prefixed point, fix(f). [3 marks] (b) Let h : P P be a continuous function on a domain P. Show that fix(h) = fix(h h). [3 marks]...
-
Fletcher, Inc. disposes of under- or over-applied overhead at year-end as an adjustment to cost of goods sold. Prior to disposal, the firm reported cost of goods sold of $619,000 in a year when...
-
During the first month of operations, these events and transactions occurred for Virmani Architects Inc.: Apr. 1 Cash of $15,000 and equipment of $6,000 was invested in the company in exchange for...
-
A student solved the following inequality incorrectly as shown. Give the correct solution set. 4x = -64 4x 4 -64 4 x < -16 Solution set: (-, -16]
-
Hooters Restaurant in Myrtle Beach, South Carolina, used an alternative dispute resolution program, a program to resolve disputes outside the traditional court system. Employees of Hooters had to...
-
The manager of the Excom Service Station wants to forecast the demand for unleaded gasoline next month so that the proper number of gallons can be ordered from the distributor. The owner has...
-
Fine Equipment uses a perpetual inventory system and is located in Vancouver, British Columbia, where the PST rate is 7 % . Fine Equipment uses the earnings approach for revenue recognition. The...
-
Determine whether the set v_1 v_2 v_3 is linearly independent. Explain. If possible find a linear dependence relation between v_1,v_2, and v_3. V = -2 O 1 V : -2 4 Vz 3 -6
-
What role does socialization play in perpetuating or challenging social inequalities, including those based on factors such as race, gender, socioeconomic status, and ability?
-
Whether the introduction of any compulsory components of corporate social responsibility would support the development of a modern company law framework?
-
A company is contemplating an investment in a new project. The company has already spent 8 0 k on a marketing study to evaluate this project. According to the study, the new online division will...
-
Mack Industries just paid a dividend of $ 3 per share ( D 0 = $ 3 ) . Analysts expect the company s dividend to grow 1 0 percent this year ( D 1 = $ 3 . 3 ) and 5 percent next year. After two years...
-
Consumers are not always aware of their rights and as such many businesses have knowingly or unknowingly violated those rights. To help address these violations several countries have established...
-
Melissa has the following items. What would be her federal income? Unemployment, $10,000 Disability income from SDI (California), $12,000 Workmans compensation, $5,000 A legal settlement of $3000 for...
-
Let (X. A. p) be a measure space. Show that for any A,B A, we have the equality: (AUB)+(An B) = (A) + (B).
-
Should the multiple regression equation be used for predicting the LDL cholesterol level based on weight and diastolic blood pressure? Why or why not? We want to consider the correlation between LDL...
-
Refer to Table 13-2 in Section 13-1 and identify the efficiency of the rank cor-relation test. What does that value tell us about the test? Table 13-2 Efficiency: Comparison of Parametric and...
-
Refer to Data Set 8 in Appendix B and use the times (seconds) that animated Disney movies showed the use of tobacco and the times that they showed the use of alcohol. Use a 0.05 significance level to...
-
Draw a diagram like that in Table 5.3, only this time assume that there are three firms, each considering the two strategies of keeping price the same or reducing it by a set amount. Identify the...
-
Having watched the clip from the film A Beautiful Mind, can you work out why the situation that Russell Crow described as being a Nash equilibrium is actually not a Nash equilibrium? Specifically, in...
-
Consider the following sequential game. Mr. New-Entrant is about to enter a market where there is an established firm run by Mrs. Incumbent. Mr. New-Entrant has to decide whether to enter the market...
Study smarter with the SolutionInn App