COMP3712/9712 Computer Programming 3 (GE) Lab 3
COMP3712/9712 Computer Programming 3 (GE) Lab 3
COMP3712/9712 Computer Programming 3 (GE) Lab 3
Lab 3: LCS and Graphs
There are two tasks for this practical: Task A and Task B. Task A examines the longest common subsequence problem using dynamic programming as discussed in Week 5. Task B examines the use of the Graph data structure discussed in week 5, 6, 7 and lays the ground work for Assignment 2. Task A and B are not dependent on each other and can be done in either order.
Task A: Longest Common Subsequence
The task in this part of the practical is to implement a solution to the longest common subsequence problem using dynamic programming as discussed in lectures.
You are provided with a skeleton NetBeans project on the lab repository that contains the framework for implementing this task. To get started you need the checkout the skeleton project from the lab code repository. The subversion code repository is based on your FAN and the lab. For example, if your FAN is blog0001, then the repository is (note the capital on Lab03):
You will find two classes: LCSTest and LCS. LCSTest contains a main method and some testing sequences to try out. LCS contains a number of methods that you need to complete the implementation of to finish the lab. LCSTest takes user input of the level of the test, followed by two strings to compare. You specify a level of 1, 2, or 3 that co
esponding the testing checkpoint 13, 14, 15 below. Initially, running the LCSTest class should result in the following output (user input bold):
3 lullabybabies skullandbones
Length of LCS = -1
LCS:
All sequences (0)
3 GTTCCTAATA CGATAATTGAGA
Length of LCS = -1
LCS:
All sequences (0)
Checkpoint 13
You need to implement the methods calculateMatrix and getLongestLength of the class LCS. You might also need to modify printMatrix if your implementation differs from mine! The supplied printMatrix method only prints the matrix not the headers. You are not required to print the headers for the checkpoint. In the output below the rows are the lullabybabies and the columns for skullandbones.
An output might look like this:
1 lullabybabies skullandbones
XXXXXXXXXX0 0 0 0
XXXXXXXXXX1 1 1 1
XXXXXXXXXX1 1 1 1
XXXXXXXXXX2 2 2 2
XXXXXXXXXX3 3 3 3
XXXXXXXXXX4 4 4 4
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 6 6
XXXXXXXXXX5 5 6 7
Length of LCS = 7
1 GTTCCTAATA CGATAATTGAGA
XXXXXXXXXX0 0 0
XXXXXXXXXX1 1 1
XXXXXXXXXX2 2 2
XXXXXXXXXX3 3 3
XXXXXXXXXX3 3 3
XXXXXXXXXX3 3 3
XXXXXXXXXX4 4 4
XXXXXXXXXX5 5 5
XXXXXXXXXX5 5 6
XXXXXXXXXX5 5 6
XXXXXXXXXX6 6 6
Length of LCS = 6
Commit your changes to the repository and take note of the revision number. Go to the Lab03, Task A, LCS Quiz on FLO and submit your revision number for Checkpoint 13.
Checkpoint 14 – Going Backwards
You need to implement the method getLCS() that returns a longest common subsequence. There might be more than one, but for this checkpoint you only need to find one of them. When you have a choice, you should move to the “left” (as shown in the lecture notes).
You should get the answers
2 lullabybabies skullandbones
XXXXXXXXXX0 0 0 0
XXXXXXXXXX1 1 1 1
XXXXXXXXXX1 1 1 1
XXXXXXXXXX2 2 2 2
XXXXXXXXXX3 3 3 3
XXXXXXXXXX4 4 4 4
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 6 6
XXXXXXXXXX5 5 6 7
Length of LCS = 7
LCS: ullabes
and
2 GTTCCTAATA CGATAATTGAGA
XXXXXXXXXX0 0 0
XXXXXXXXXX1 1 1
XXXXXXXXXX2 2 2
XXXXXXXXXX3 3 3
XXXXXXXXXX3 3 3
XXXXXXXXXX3 3 3
XXXXXXXXXX4 4 4
XXXXXXXXXX5 5 5
XXXXXXXXXX5 5 6
XXXXXXXXXX5 5 6
XXXXXXXXXX6 6 6
Length of LCS = 6
LCS: CTAATA
If you go up or randomly choose a direction you might get the longest common subsequence of GTTTAA or GTAATA. For this checkpoint, got to the “left” to match the output above.
Commit your changes to the repository and take note of the revision number. Go to the Lab03, Task A, LCS Quiz on FLO and submit your revision number for Checkpoint 14.
COMP3712/9712 Computer Programming 3 (GE) Lab 3
COMP3712/9712 Computer Programming 3 (GE) Lab 3
COMP3712/9712 Computer Programming 3 (GE) Lab 3
Page 1 of 11
Page 1 of 11
Page 1 of 11
Checkpoint 15 – Going Backwards (Going Backwards) - Super Hard!
You need to implement the methods getAllLCS() that returns ALL the unique longest common subsequences in lexicographic order (as define by the String classes compareTo method). We have not explicitly discussed how to do this in lectures. You need to figure it out yourself (e.g. try Wikipedia)! Note that there are many possible ways to get the single “ullabes” sequence, but return only one.
You should get the answers
3 lullabybabies skullandbones
XXXXXXXXXX0 0 0 0
XXXXXXXXXX1 1 1 1
XXXXXXXXXX1 1 1 1
XXXXXXXXXX2 2 2 2
XXXXXXXXXX3 3 3 3
XXXXXXXXXX4 4 4 4
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 5 5
XXXXXXXXXX5 5 6 6
XXXXXXXXXX5 5 6 7
Length of LCS =
7 LCS: ullabes All sequences (1) ullabes
3 GTTCCTAATA CGATAATTGAGA
XXXXXXXXXX0 0 0
XXXXXXXXXX1 1 1
XXXXXXXXXX2 2 2
XXXXXXXXXX3 3 3
XXXXXXXXXX3 3 3
XXXXXXXXXX3 3 3
XXXXXXXXXX4 4 4
XXXXXXXXXX5 5 5
XXXXXXXXXX5 5 6
XXXXXXXXXX5 5 6
XXXXXXXXXX6 6 6
Length of LCS =
6 LCS: CTAATA
All sequences (3)
CTAATA
GTAATA GTTTAA
c
Task B: Graphs and Topological Sort
Checkpoint 16: Adjacency List Graph Implementation
You are supplied with Graph abstract class that defines a number of essential methods for operating on graphs.
To get started you need the checkout the skeleton project from the lab code repository. The subversion code repository is based on