Description and files needed/Undirected folder/undirected2.txt 9 2 4 5 3 2 3 6 2 1 3 2 1 2 2 0 6 2 0 6 3 1 4 5 1 8 1 7 Description and files needed/mutant folder/mutant2.txt 5 9 baa abcd cab eba eca...

1 answer below »
The description is provided in the file below, So that will be your entire guide during the process. The code should be done in java. I would like this done by this week Wednesday.
A lot of the code/s are already done for you, so it's not that long. You just have to do the "complete this method" sections.



KEEP IN MIND:
Be cautious of the "DO NOT" criteria that I outlined in the description file.


Description and files needed/Undirected folder/undirected2.txt 9 2 4 5 3 2 3 6 2 1 3 2 1 2 2 0 6 2 0 6 3 1 4 5 1 8 1 7 Description and files needed/mutant folder/mutant2.txt 5 9 baa abcd cab eba eca cba daa abb bcd Description and files needed/mutant folder/mutant1.txt 5 9 baa abc abca cabe cad eba ecada dba daae Description and files needed/unweighted folder/unweighted1.txt 7 3 1 3 4 3 0 2 3 2 1 3 4 0 1 2 6 2 0 5 2 4 6 2 3 5 Description and files needed/Undirected folder/undirected1.txt 8 3 4 5 6 2 2 3 2 1 3 2 1 2 2 0 6 2 0 6 3 0 4 5 0 Description and files needed/unweighted folder/unweighted2.txt 7 2 1 3 3 0 2 3 2 1 3 4 0 1 2 5 3 0 5 6 1 3 1 4 Description and files needed/mutant folder/mutant3.txt 7 14 baa dbbb dbac dbacd abcd aade faab feabc cab caef gdfg gagfr ea eae Description and files needed/(2) ExpectedOutput.pdf *** Test Mutant Language 1 *** Alphabet order: [b, a, c, e, d] *** Test Mutant Language 2 *** Unfortunately, this language has circular dependency. *** Test Mutant Language 3 *** Alphabet order: [b, d, a, f, c, g, e] *** Test BFS on UnweightedGraph 1 *** Level array (from v0): [0, 1, 2, 1, 1, 2, 2] Level array (from v1): [1, 0, 1, 1, 2, 3, 2] Level array (from v2): [2, 1, 0, 1, 3, 3, 2] Level array (from v3): [1, 1, 1, 0, 2, 2, 1] Level array (from v4): [1, 2, 3, 2, 0, 1, 2] Level array (from v5): [2, 3, 3, 2, 1, 0, 1] Level array (from v6): [2, 2, 2, 1, 2, 1, 0] *** Test BFS on UnweightedGraph 2 *** Level array (from v0): [0, 1, 2, 1, infty, 2, infty] Level array (from v1): [1, 0, 1, 1, infty, 2, infty] Level array (from v2): [2, 1, 0, 1, infty, 2, infty] Level array (from v3): [1, 1, 1, 0, infty, 1, infty] Level array (from v4): [1, 2, 3, 2, 0, 1, 1] Level array (from v5): [2, 2, 2, 1, infty, 0, infty] Level array (from v6): [2, 3, 4, 3, 1, 2, 0] *** Test Transitive Closure on UnweightedGraph 1 *** [true, true, true, true, true, true, true] [true, true, true, true, true, true, true] [true, true, true, true, true, true, true] [true, true, true, true, true, true, true] [true, true, true, true, true, true, true] [true, true, true, true, true, true, true] [true, true, true, true, true, true, true] *** Test Transitive Closure on UnweightedGraph 2 *** [true, true, true, true, false, true, false] [true, true, true, true, false, true, false] [true, true, true, true, false, true, false] [true, true, true, true, false, true, false] [true, true, true, true, true, true, true] [true, true, true, true, false, true, false] [true, true, true, true, true, true, true] *** Test Transitive Closure on UndirectedGraph 1 *** [true, false, false, false, true, true, true, false] [false, true, true, true, false, false, false, false] [false, true, true, true, false, false, false, false] [false, true, true, true, false, false, false, false] [true, false, false, false, true, true, true, false] [true, false, false, false, true, true, true, false] [true, false, false, false, true, true, true, false] [false, false, false, false, false, false, false, true] *** Test Transitive Closure on UndirectedGraph 2 *** [true, true, true, true, true, true, true, false, false] [true, true, true, true, true, true, true, false, false] [true, true, true, true, true, true, true, false, false] [true, true, true, true, true, true, true, false, false] [true, true, true, true, true, true, true, false, false] [true, true, true, true, true, true, true, false, false] [true, true, true, true, true, true, true, false, false] [false, false, false, false, false, false, false, true, true] [false, false, false, false, false, false, false, true, true] *** Test DFS on UnweightedGraph 1 *** Level array (from v0): [0, 6, 5, 4, 1, 2, 3] Level array (from v1): [5, 0, 2, 1, 4, 3, 2] Level array (from v2): [5, 6, 0, 1, 4, 3, 2] Level array (from v3): [4, 5, 6, 0, 3, 2, 1] Level array (from v4): [6, 5, 4, 3, 0, 1, 2] Level array (from v5): [5, 4, 3, 2, 6, 0, 1] Level array (from v6): [3, 6, 5, 4, 2, 1, 0] *** Test DFS on UnweightedGraph 2 *** Level array (from v0): [0, 3, 2, 1, infty, 2, infty] Level array (from v1): [2, 0, 2, 1, infty, 2, infty] Level array (from v2): [3, 2, 0, 1, infty, 2, infty] Level array (from v3): [3, 2, 1, 0, infty, 1, infty] Level array (from v4): [5, 4, 3, 2, 0, 1, 1] Level array (from v5): [4, 3, 2, 1, infty, 0, infty] Level array (from v6): [6, 5, 4, 3, 1, 2, 0] *** Test Component Counter on UndirectedGraph 1 *** Number of components is 3 *** Test Component Counter on UndirectedGraph 2 *** Number of components is 2 *** Test Tree Traversals *** Pre-order Traversal: 22 8 14 0 6 5 70 20 11 16 24 8 20 In-order Traversal: 0 14 5 6 70 8 20 11 22 24 16 8 20 Post-order Traversal: 0 5 70 6 14 11 20 8 24 20 8 16 22 *** Test Rotated Array *** Array is: [8, 10, 14, 17, 19, 21, 1, 3, 5, 6] Maximum is at index: 5 Key 8 found at index 0 Key 9 not found Key 13 not found Key 14 found at index 2 Key 15 not found Key 17 found at index 3 Key 18 not found Key 19 found at index 4 Key 20 not found Key 21 found at index 5 Key 24 not found Key 1 found at index 6 Key 2 not found Key 3 found at index 7 Key 4 not found Key 5 found at index 8 Key 6 found at index 9 Key 7 not found Key 9 not found Key 10 found at index 1 Key 12 not found Array is: [10, 1, 5, 7] Maximum is at index: 0 Key 8 not found Key 10 found at index 0 Key 12 not found Key 0 not found Key 1 found at index 1 Key 3 not found Key 5 found at index 2 Key 6 not found Key 7 found at index 3 Key 9 not found Array is: [12, 1, 5, 7, 10, 11] Maximum is at index: 0 Key 8 not found Key 10 found at index 4 Key 11 found at index 5 Key 12 found at index 0 Key 0 not found Key 1 found at index 1 Key 3 not found Key 5 found at index 2 Key 6 not found Key 7 found at index 3 Key 9 not found Array is: [12, 10, 11] Maximum is at index: 0 Key 8 not found Key 10 found at index 1 Key 11 found at index 2 Key 12 found at index 0 Key 15 not found Array is: [12, 1] Maximum is at index: 0 Key 0 not found Key 1 found at index 1 Key 4 not found Key 12 found at index 0 Key 14 not found Description and files needed/(1) Description (1).pdf (Topological Sorting, Breadth First Search, Depth First Search, and Recursion) 1: Overview We are going to: ● Use Topological Sorting to help mutants. ● Implement Breadth First Search, and use it to compute the transitive closure. ● Implement Depth First Search, and use it to count the number of components. ● Use recursion for various problems. To this end, your task is to implement the following methods: ● readLanguage, makeGraph, and getOrder in MutantLanguage.java ● execute, and computeTransitiveClosure in BFS.java ● init, run, execute, and countComponents in DFS.java ● preOrder, inOrder, postOrder, rotatedBinarySearch, and maxIndex in Recursion.java The project also contains additional files (which you do not need to modify). Use TestCorrectness.java to test your code. For each part, you will get an output that you can match with the output I have given to verify whether your code is correct, or not. Output is provided separately in the ExpectedOutput file. Should you want, you can use www.diffchecker.com to tally the output. 2: Java In-built Linked List We will use the inbuilt linked-list of Java. This is an implementation of a doubly-linked-list (with links going both forward and backward). It supports all the standard operations (inserting at front or end, deleting head or tail, traversing the list, etc.) I’ll highlight some of the usages (not
description-and-files-needed-zc5x1euh.zip
Answered 1 days AfterJun 15, 2021

Answer To: Description and files needed/Undirected folder/undirected2.txt 9 2 4 5 3 2 3 6 2 1 3 2 1 2 2 0 6 2 0...

Rushendra answered on Jun 16 2021
149 Votes
Description and files needed/(1) Description (1).pdf
(Topological Sorting, Breadth First Search, Depth First
Search, and Recursion)
1: Overview
We are going to:
● Use Topological Sorting to help mutants.
● Implement Breadth First Search, and use it to compute the transitive closure.
● Implement Depth First Search, and use it to count the number of components.
● Use recursion for various problems.
To this end, your task is to implement the following methods:
● readLanguage, makeGraph, and getOrder in MutantLanguage.java
● execute, and computeTransitiveClosure in BFS.java
● init, run, execute, and countComponents in DFS.java
● preOrder, inOrder, postOrder, rotatedBinarySearch, and maxIndex in
Recursion.java
The project also contains additional files (which you do not need to modify).
Use TestCorrectness.java to test your code.
For each part, you will get an output that you can match with the output I have given to verify
whether your code is correct, or not. Output is provided separately in the ExpectedOutput file.
Should you want, you can use www.diffchecker.com to tally the output.
2: Java In-built Linked List
We will use the inbuilt linked-list of Java. This is an implementation of a doubly-linked-list (with
links going both forward and backward). It supports all the standard operations (inserting at front
or end, deleting head or tail, traversing the list, etc.)
I’ll highlight some of the usages (not all may be required). Typically, this encompasses use of
generics (in Java), whereby you can create linked lists of any type (and not just integer). I will
discuss integer linked lists, but lists of any type can be created; in fact, you
will be using linked lists of type Edge. The syntax will remain pretty much the same, and this
description file contains enough details on how to adapt for Edge type linked lists. Check the
UnderstandingLinkedList.java file for examples.
2.2: Java
● Syntax to create an integer list: LinkedList nameOfList = new LinkedList();
● To get the size of the list, the syntax is: nameOfList.size();
● To add a number at the end, the syntax is: nameOfList.addLast(15); To add a number at
the beginning, the syntax is: nameOfList.addFirst(15);
● To remove the last number, the syntax is: nameOfList.removeLast(); To remove the first
number, the syntax is: nameOfList.removeFirst();
To traverse the list (say for retrieving a value or searching or printing or deleting), one can
use an iterator as shown next. Here, print method prints the list.
2
static void print(LinkedList numbers) { // printing the content
Iterator it = numbers.iterator();
while (it.hasNext())
System.out.print(it.next() + " ");
}
● Iterator it = numbers.iterator(); declares an iterator it on the list numbers and the
iterator points to the first number on the list.
● while (it.hasNext()) ensures that the iterator traverses until the end of the list is reached.
● it.next() retrieves the value of the node at which the iterator is pointing as well as moves
the iterator to the next node. Thus System.out.print(it.next()) prints the value of the node
at which the iterator is pointing, and then moves the iterator to the next node.
3: Java Dynamic Arrays
Here, you will use their Java implementations of dynamic arrays, which are named respectively
vector and ArrayList. This involves the use of generics/templates. I will discuss this in the context
of integers, but you will be using vectors/array-lists of Edge-type linked-lists; you will find enough
details in this description pdf for this usage.
Check the UnderstandingArrayList.java file for examples.
• In Java, to create an integer ArrayList use: ArrayListhIntegeri name = new ArrayListhIntegeri(); To add
a number (say 15) at the end of the array list, the syntax is name.add(15).
Although not needed for this assignment, the following are good to know. To remove the
last number, the syntax is name.remove(name.size() – 1). To access the number at a
particular index (say 4), the syntax is name.get(4).
Note that the push back and add functions are equivalent to insertAtEnd, whereas pop back
and remove (with the appropriate index) are equivalent to deleteLast.
4: Graph Data
To test BFS and DFS, we use the graphs in files: unweighted1.txt, and unweighted2.txt. To
test ComponentCounter, we use the graphs in files: undirected1.txt, and undirected2.txt. To
test TransitiveClosure, we use all four graphs. Next, a description is given. (To test topological
sorting, we use: mutant1.txt and mutant2.txt
4.1: Unweighted Graph File Structure
Consider the first graph; the file unweighted1.txt represents this graph. The first line in
the file stores the number of vertices, which is 7. Then, there are 7 lines, representing v0 through
v6. The first number in each line is the number of outgoing edges of that vertex. Then, we have
the vertices to which each outgoing edge leads. For e.g., in line 2 (i.e., 3 1 3 4): the first number
is 3, indicating vertex v0 has 3 outgoing edges to the vertices v1, v3, and v4 respectively.
4.2: Adjacency List: Representing Graphs in Memory
The vertices in the graph are numbered 0 through n − 1, where n is the number of vertices. We
use adjList (called adjacency list) to represent the graph; this is conceptually similar to a two
dimensional jagged array, with the difference that each row is implemented using a linked list.
Specifically, row index i in the array corresponds to the vertex vi, i.e., row 0 corresponds to v0,
row 1 corresponds to v1, and so on.
Each row is a linked list of type Edge, and each node in the linked list for row i stores an
outgoing edge of the vertex vi. Each edge has 2 properties – src, and dest, which are
respectively the vertex from which the edge originates, and the vertex where the edge leads to.
As an example, consider the first graph in the previous page. Row 0 of adjList contains the
following edges: ; this is to be interpreted as vertex v0 has 3< 0, 1 >, < 0, 3 >, ??? < 0, 4 >
outgoing edges – one edge to the vertex v1, one to the vertex v3, and another to vertex v4.
Likewise, row 1 contains the edges . Likewise, for the other< 1, 0 >, < 1, 2 >, ??? < 1, 3 >
vertices/rows.
In a nutshell, Edge is a class which has two integer variables – src, and dest. The adjList
structure in the Graph class, therefore, is a dynamic array of linked lists, where each node in the
linked-list is of type Edge. In Java, we implement adjList as an array-list of Edge linked-lists.
The only difference in this implementation is that you are using linked lists for each row, instead of
(dynamic) arrays. See the Graph.java files for the structure of the graph (i.e., how it is stored in the
memory). Also, see UnderstandingAdjacencyList.java
files for how an adjacency list (as formulated in Graph.java) works for a particular graph (the first
one in the previous page).
5: Implementing Stack with a Linked List
You will need to implement a stack using the in-built linked-list. This will be needed for the DFS
portion of the code. You have already seen the logic; so, I will get into the syntax directly.
5.2: Java
● CREATE: List name = new LinkedList<>();
● SIZE: name.size();
● PUSH: name.addLast(15);
● POP: name.removeLast(); to retrieve and remove the last number.
6: Implementing Queue with a Linked List
6.2: Java
● CREATE: List name = new LinkedList<>();
● SIZE: name.size();
● ENQUEUE: name.addLast(15);
● DEQUEUE: name.removeFirst(); to retrieve and remove the first number.
7: Mutant Language
Professor Xavier is trying to develop a new language for fellow mutants. As with any language,
the main constituent are words via which one can effectively communicate with one another.
However, the language is new, and mutants are not yet conversant about the meaning of the
words; therefore, professor Xavier has to design a standard dictionary which will map mutant
words to their English meaning. Since fellow mutants need to be able to search the dictionary,
the Professor needs to make sure that words can be ordered (like a normal English dictionary).
Therefore, after creating the words, Professor Xavier needs to ensure that there are no cyclic
dependencies. Being sympathetic to the mutant cause, we want to help Professor to make sure
that the language is meaningful.
To test, we use the language in files: mutant1.txt, mutant2.txt and mutant3.txt. Next, a
description of the files are given.
7.1: File Description
The first line contains two numbers. The first is the number of distinct characters in the language.
For example, in mutant1.txt, it is 5 (the distinct characters being {a, b, c, d, e}). The second is
the number of words in the language; here, it is 9. Then, we have the 9 words of the language.
7.2: Comparing Strings
Before proceeding further, recall how you compare strings lexicographically (i.e., dictionary order
wise). You match the strings one character at a time, until you find a mismatch (or exhaust one of
the strings). The lexicographically smaller string is the one with the smaller mismatched
character (or the shorter one if you exhaust one string).
6
7.3: Assumptions
For the sake of simplicity, we assume that the words contains letter from the lower-case English
alphabet in a contiguous way. Specifically, it contains the letters starting from a and we will not
skip a letter. We will also assume that all words are distinct. Also, Professor Xavier makes sure
that if there are two words X and Y , where X is a prefix of Y (such as X = abc and Y = abca), she
always places X before Y . If that were not the case, more complications arise.
7.4: What we need to ensure?
We have to make sure that the words in the language can be ordered in a dictionary. In other
words, the first word must be lexicographically smaller than the second, the second smaller than
the third, and so on. However, since this is a new language, it is no longer necessary that a is
smaller than b, and b is smaller than c, and so on. We are perfectly happy as long as we can
somehow order them , and we do not create a cycle(???ℎ ?? ? < ? < ? < ? < ?)
(???ℎ ?? ? < ?, ? < ?, ??? ? < ?).
7.5: How do we do it?
To verify the correctness of the language, we create a graph as follows. For each distinct letter,
you create a vertex. Specifically, a corresponds to the vertex...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?