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)
Solutions Step 1 Dynamic Programming is basically a technique in computer programming that mostly he... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
The engine block of a small electric generator gets very hot during operation. It is needed to remove as much heat as possible from the top surface of the block while keeping its temperature at a...
-
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...
-
Poisons are used to prevent rat damage in sugarcane fields. The U.S. Department of Agriculture is investigating whether the rat poison should be located in the middle of the field or on the outer...
-
Comets move around the sun in very elliptical orbits. At its closet approach, in 1986, Comet Halley was 8.79 10 7 km from the sun and moving with a speed of 54.6 km/s. What was the comets speed when...
-
In a cycle, every vertex has degree two. a. True b. False
-
Accounting for bonds using amortized cost measurement based on the historical market interest rate. OBrien Corporation issues $8,000,000 face value, 8% semiannual coupon bonds maturing in 20 years....
-
Only the IPOs for large corporations are sold in primary markets.
-
Bangs Leisure Chairs produces three types of hand-crafted outdoor chairs: sling chairs, Adirondack chairs, and hammocks. After reviewing the labor required for each type of chair, the following...
-
A local gas station is looking to measure the proportion of customers who purchase diesel fuel at the pump. They decided to conduct a study on 375 customers that bought gas at the station and...
-
1. An office manager of a local health care practice with several primary care physicians. Hired a new supervisor and are reviewing the practice policy on licensure. Explain to the new supervisor...
-
Why do you think Fink has made this written announcement declaring BlackRock's view on linking purpose to profits? (on the page 10 of case)...
-
Sanjana's Sweet Shoppe operates on the boardwalk of a New England coastal town. The store only opens for the summer season and the business is heavily dependent on the weather and the economy in...
-
An investor forms a portfolio of two stocks, Alpha and Beta. Information regarding the two stocks is shown below: Stock Expected Return Alpha 6% Standard Deviation 25% 30% Bravo 8% The correlation...
-
Wonder Inc. has invented a new machine. The company wants to lease its machines, but it is yet to finalize the terms for leasing. The marginal cost of running a machine is $30 per hour. The estimated...
-
The adjusted trial balance is prepared a. After adjusting entries have been journalized and posted b. After financial statements are prepared. O c. Before the trial balance Od. To prove the equality...
-
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...
-
Esteban Almada was recently promoted to loan officer at First Federal Bank. He has authority to issue loans up to $75,000 without approval from a higher bank official. This week two small companies,...
-
Refer to CVS Corporations annual report in the Supplement to Chapter 1 to answer the following questions. (Note that 2004 refers to the year ended January 1, 2005, and 2003 refers to the year ended...
-
Review the multistep income statement presented in Exhibits 3 and 4. In your group, discuss how this form of the income statement meets each of these qualitative characteristics of accounting...
Study smarter with the SolutionInn App