A. DAG TEST
Given an edge list of a directed graph, the task is to test whether the graph is acyclic or not.
Input:
The input is in ‘TestGraph.txt’. Each line contains the source and target string separated by ‘,’. The ‘END’denotes the end of the edge list. The following input contains two graphs. Sample input:
2,4
4,3 4,6 END
2,3
3,4
4,2
END
Output:
Each line of the output contains True or False, depending on whether the graph is a DAG or not.
Sample output:
TRUE
FALSE
Instructions:
Edit the given code TestGraph.java to complete the assignment. Do not edit the part which is READ ONLY. Submit TestGraph.java in Moodle. Note that you need to carefully read the given print function to understand how you can traverse a graph with the given graph data structure.
B. Constrained Edit distance
In this question we are trying to solve the edit distance problem from the book (by insertion, deletion, substitution), but avoiding same operation applied consecutively.
For example, if the input is (APPLE,MAPLE), then the following transformation is invalid: APPLE (deletion) APLE (deletion) PLE (insertion) MPLE (insertion) MAPLE. There is another invalid transformation with cost 2: APPLE (substitution) MPPLE (substitution) MAPLE.
A valid sequence would be APPLE (deletion) APLE (insertion) AMPLE (deletion) MPLE (insertion) MAPLE. However, this is not a minimum cost solution. There is another valid transformation with cost 3: APPLE (substitution) MPPLE (deletion) MPLE (insertion) MAPLE.
Consider another example (GO,ALGORITHM). In this case there is no valid solution. Because, you have to perform at least 7 insertions, so there is no way you can avoid consecutive insertions.
Modify the recurrence provided in the book for the edit distance algorithm. For more input output see the official page in piazza.
Input:
The input is in ‘edit.txt’. Each line contains the source and target string separated by ‘,’. Sample input:
APPLE,MAPLE
GO,ALGORITHM
Output:
Each line of the output contains the cost, which is the edit distance cost for the corresponding input. If there is no valid solution, then the output is -1. Sample output:
2
-1
Instructions:
Edit the given code Edit.java to complete the assignment. Do not edit the part which is READ ONLY. Submit Edit.java in Moodle.
