Description
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
1
Assignment 2 — Posted October 28,— Submission Deadline: See Moodle
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
2
Assignment 2 — Posted October 28,— Submission Deadline: See Moodle
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.
3