Description
In this lab, you will implement a brute-force algorithm for the longest common subsequence problem (LCS) using a Bag. You will be using the Bag without delving into the details of how the class is implemented; that is, you will be wri ng client code.
The primary goal of this lab is to prac ce solving problems using the methods provided by a data structure. A secondary goal is to familiarize yourself more deeply with the ADT Bag and its poten al uses.
The ADT Bag is one of the primary collec on structures defined in mathema cs. Also called a mul set, it is a generaliza on of a set that is allowed to hold mul ple copies of an item. Like a set, the items contained within the set have no par cular ordering. Before comple ng this exercise you should review the methods available to you in the Bag ADT.
Your TA will give a lesson reviewing the ADT Bag and introducing the longest common subsequence problem.
Exercise
A er the TA’s lesson, complete the following steps:
-
Download the provided code, located on the course website where the following java files are provided.
BagInterface.java is a Java interface represen ng the ADT Bag.
ArrayBag.java is a dynamic capacity array-based implementa on of ADT Bag. You will not need to focus on this implementa on in this exercise. LongestCommonSubsequence.java provides the skeleton of a LCS solu on.
Note that all of these files are in the package cs445.lab2 . Review Lab 1 if you do not remember how to handle code in packages.
-
Review the following algorithm that finds the LCS of two input strings. This algorithm takes a brute force approach of genera ng all possible subsequences and checking them. Note that, while this algorithm will get the correct answer, a more efficient approach would be to use dynamic programming (a topic from CS 1501).
Longest Common Subsequence (first, second):
Create an empty bag
Put the first string into the bag
Set the longest subsequence to the empty string
While the bag is not empty:
Remove a test string from the bag
If the the longest subsequence is shorter than the test string:
If the test string is a subsequence of the second string:
Set the longest subsequence to the test string
Otherwise, if test is at least 2 longer than longest subsequence:
Generate new strings from test by removing each single charact
Put each of the new strings in the bag
Print the Bag of strings that need to be checked Print out the longest subsequence
Note that LongestCommonSubsequence.java already contains a method, isSubsequence , to check whether one string is a subsequence of another.
3. Once you understand the algorithm from Step 2, read through LongestCommonSubsequence.java , no ng the 2 TODO comments. You will need to complete these por ons of the code.
-
At the first TODO comment, create a new bag of strings, assign it to the variable possibleSubsequences , and add the string first to the bag.
-
At the second TODO comment, implement the algorithm from Step 2.
-
Test the program to be sure it works. Below are pairs of strings and their correct longest common subsequence.
-
First
Second
LCS
-
ABC
|
AA |
ABA |
AA |
|
First |
Second |
LCS |
|
AA |
AAA |
AA |
|
AABC |
ABBC |
ABC |
|
ABBC |
ABCC |
ABC |
|
ABCC |
CABAC |
ABC |
|
ABA |
AA |
AA |
|
ABC |
CBACBA |
AB or BC or AC |
|
ABC |
CBACBACBA |
ABC |
|
ABC |
BCABCA |
ABC |
|
ABCD |
DCBADCBA |
AB or AC or AD or BC or BD or CD |
|
ABFCD |
ADBAFDCBA |
ABFC or ABFD |
|
ABFCD |
ADBADCBA |
ABC or ABD |
|
ABCDF |
ADBADCBA |
ABC or ABD |
|
ABADA |
BADABAABDBA |
ABADA |
Conclusion
In this lab, you wrote client code using the ADT Bag to solve the LCS problem. Wri ng client code is a crucial skill in Data Structures. Throughout the term, you should take the
me to prac ce wri ng code that uses the data structures presented. to improve your skills in solving problems using the (o en limited set of) opera ons available to you.
