Lab 2: Bag Client Solution

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:

    1. 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.

    2. 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.

    4. 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.
    5. At the second TODO comment, implement the algorithm from Step 2.

    6. 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.