Answer To: pa/(1) Description (1).pdf (Topological Sorting, Breadth First Search, Depth First Search, and...
Kashyap answered on Jun 21 2021
pa/(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 v0, b corresponds to the vertex v1,
and so on. We scan each word one-by-one and compare it to the next one character at a time.
Suppose, the first character where the current word mismatches the next one are α and β
respectively. Then, we draw an edge from the vertex corresponding to α to the vertex
corresponding to β. In mutant1.txt, we compare baa and abc first. Since , we draw an? ≠ ?
edge from v1 to v0. Now, we compare abc and abca; since no mismatch occurs (before we
exhaust a word), we do not create an edge. Then, we compare abca and cabe; since a ,? ≠ ?
we draw an edge from v0 to v2. Next we compare cabe and cad; the first two characters match,
but then b , and we draw an edge from v1 to v3. We proceed like this until we exhaust all? ≠ ?
the words. See next page for an illustration.
Now, the language is valid (i.e., we can create a dictionary with the words) if the graph
formed is acyclic; in that case, the precedence order of the characters is given by a topological
order of the graph. To detect whether or not the graph is acyclic, we apply topological sorting.
7.6: Why does it work?
Observe that whenever we find a mismatch, we draw an edge from the mismatched character of
current word to that of next word. Hence, if the graph contains a cycle, then it must mean that
there are words X1, X2, . . . , Xk in the language where X1 is smaller than X2, X2 is smaller than
X3, and so on until Xk is smaller than X1 (because the first mismatched character of X1 is smaller
than X2, that of X2 is smaller than X3, and so on until that of Xk is smaller than X1). If the graph
does not contain a cycle, it must mean that we can order the words lexicographically.
7.7: Example of an invalid language
In mutant1.txt, the graph is acyclic and we have a valid topological order. On the other hand, in
mutant2.txt, if you choose the words abcd, cab, daa, and abb, you realize that there is no way to
order these words in that order because that implies a < c < d < a. If you look at the
corresponding graph, it has the cycle a → c → d → a; there are other cycles as well such as a →
b → a. As long as there is one cycle, the language is not valid.
7.8: Using ASCII to map character to vertex
One thing to note is that we have to map lower-case English characters (a, b, c, . . . ,) to vertex
numbers (0, 1, , 2, . . . ,). This is because our Graph structure uses integers as vertices (which
start at zero). What we essentially do is use the ASCII value of the character and subtract 97 to
map it to its rank among the lower-case letters of the English alphabet. The ASCII value of a is
97, b is 98, and so on; see http://www.asciitable.com/ for the full ASCII table. Therefore, if we
have the characters a, b, c, d, and e, then they are mapped respectively to 0, 1, 2, 3, and 4
(corresponding to the vertices v0, v1, v2, v3, and v4).
Likewise, once we get the vertex order (integer values), we transform them to the actual
characters by adding 97 to get the ASCII value and typecasting to char.
7.9: One final thing before we move to code
One thing you may have observed is that we can add multiple edges from one vertex to another
vertex. For example in mutant3.txt, we add two edges from b to a. This is because the words
dbbb and dbac add one edge, and the words abcd and aade add another edge. There is no
reason to add both the edges, but trying to avoid that would mean that we scan the outgoing
edges of b to make sure an edge to a is not already added (or use specialized structures such as
a hashtable to maintain the outgoing edges). Having multiple edges, however, does not cause
any harm (in the sense that it does not induce any new cycle) and both edges will be relaxed
when we process the vertex b. So, once again, in the interest of keeping things simple, we add
multiple edges.
7.10: Pseudo-code
First, implement the readLanguage method. You’ll find similar syntax in readUnweightedGraph
and readWeightedGraph methods in Graph.java file.
Reading mutant file
● Java: Create a Scanner object f ileReader on f ileP ath. To create a scanner on a
file x.txt: Scanner fileReader = new Scanner(new FileInputStream(“x.txt”));
● Read the number of distinct characters into the class-variable numV ertices. Java:
Syntax to read a value into an integer variable x is: x = fileReader.nextInt();
● Now, read the number of words in the language into the class-variable numW ords
● Allocate numW ords cells for the class-array words. Note that words is a string
array.
● Run a for loop from i = 0 to i < numWords. Within the for-loop, use f ileReader to
read the line into the array cell words[i].
Java: Syntax to read into a string variable y is: y = fileReader.next();
● After the loop, close fileReader.
Notice that the first number on the file is read as the number of vertices in the graph, as
desired. Now, we will create the graph based on the idea discussed previously. A detailed
pseudo-code is given below to achieve the same. Use it to implement the makeGraph() method.
You’ll find similar syntax in the readUnweightedGraph method in Graph.java file. Creating the
graph
Creating the graph
● Allocate numV ertices cells for inDegree array.
● Allocate numV ertices rows for adjList.
○ Java syntax: adjList = new ArrayList<>(numVertices);
● for (i = 0 to i < numV ertices), do the following:
○ set inDegree[ ] to 0
○ add a blank row to adjList
Java syntax: adjList.add(new LinkedList());
Adding this blank row is necessary so that we have reserved a row for each vertex,
which will save us from a null pointer exception if we try to access an empty row
(i.e., a vertex with no outgoing edges) later on.
● • for (i = 0 to i < numW ords − 1), do the following:
○ let currentWord be the word at index i of words[ ] array
○ let nextWord be the word at index i + 1 of words[ ] array
○ let minLength be the minimum of the lengths of currentWord and nextWord. That is,
if the lengths of currentWord and nextWord are 7 and 5 respectively, then minLength
= 5, and vice-versa. Ties are broken arbitrarily.
Java syntax for length of a string named str: str.length()
○ Now, we want to find the first character where currentWord and nextWord mismatch.
Let this character be x and y respectively. We want to draw an edge from the vertex
for x to the vertex for y. Since x and y are lower-case characters with ASCII values
starting from 97, and the graph can only support integers...