Programming Assignment 4 (Longest Paths in DAG, Bellman-Ford,
All-Pair Shortest Paths, Minimum Spanning Trees, and
Knuth-Mo
is-Pratt)
Department of Computer Science, University of Wisconsin – Whitewate
Theory of Algorithms (CS 433)
Instructions For Submissions
• This assignment is to be completed individually. If you are stuck with something,
consider asking the instructor for help.
• Submission is via Canvas as a single zip file.
• Any function with a compilation e
or will receive a zero, regardless of how much
it has been completed.
1 Overview
Your task is to implement the following methods:
• longestPaths in DAG
• execute in BellmanFord
• execute in Johnson
• execute in FloydWarshall
• runDJP in DJP
• the constructor, makeSet, find, append, and doUnion methods in UnionFind
• runKruskal in Kruskal
• runKMP and computeFailure in KMP
The project also contains additional files which you do not need to modify (but need to use).
1.1 Testing Co
ectness
Use TestCo
ectness file 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 or not your code is co
ect. Output is provided
in the ExpectedOutput file. You can use www.diffchecker.com to tally the output.
www.diffchecker.com
To test the co
ectness of the longest paths algorithm, I have included 2 sample files: dag1.txt,
and dag2.txt. To test the co
ectness of Bellman-Ford, I have included 3 sample files: bellmanford1.txt,
ellmanford2.txt, and bellmanford3.txt. To test the co
ectness of Dijkstra, I have included
2 sample files: dijkstra1.txt, and dijkstra2.txt. To test the co
ectness of Johnson and
Floyd-Warshall, I have included 3 sample files: apsp1.txt, apsp2.txt, and apsp3.txt. The cor-
esponding graphs are shown below.
Each .txt file has the following format. First line contains the number of vertices and edges
espectively. Second line onwards are the edges in the graph; in particular, each line contains three
entries: the source vertex, the destination vertex, and the length of the edge.
v0 v1 v2
5 −5
v0 v1 v2
v3
v4
v5 v6 v7
4
4
2
5 12
10 3
−7
−5
−10
12
Figure 1: Graphs used for Testing DAG Longest Paths Algorithm
v0
v2
v1 v3
v4
6
5
-2 -4
-3
7
9
8
7
2
v0
v2
v1 v3
v4
5
-2 -4
-3
7
9
8
7
2
-6
v1v2v3 v0v4v5
XXXXXXXXXX
Figure 2: Graphs used for Testing Bellman-Ford Algorithm
v0
v2
v1
v3
10
0 5
17
v4
3
2
7
17
v6
7
v5
3
2
v0
v2
v1
v3
10
0 5
v4
17
1
2
v6
7
v5
7
2
3
Figure 3: Graphs used for Testing Dijkstra’s algorithm
To test the co
ectness of your MST implementations, I have included: mst graph.txt; the co
e-
sponding graphs and MST are shown next.
2
v0
v2
v1 v3
v4
5
-2 -4
-3
7
9
8
7
2
-6
v0
v2
v1 v3
v4
6
5
-2 -4
-3
7
9
8
7
2
v0
v1
v3
6
-9
15
8
v5-8
v4
7
-20
v2
Figure 4: Graphs used for Testing All-Pair Shortest Paths Algorithm
v0
v1 v2 v3
v7
v8
v6 v5
v4
4
8
11
47
1 2
2
6
8 7
10
14
9
v0
v1 v2 v3
v7
v8
v6 v5
v4
4
8
4
1 2
2
7
9
Figure 5: Graph (left) used for testing MST algorithms; co
esponding MST on right
1.2 C++ Helpful Hints
Use DYNAMIC ALLOCATION for declaring any and all a
ays/objects. Remember to return an
a
ay from a function, you must use dynamic allocation. So, if you want to return an a
ay x
having length 10, it must be declared as int *x = new int[10];
1.3 Multidimensional a
ays
A 2d a
ay is one which has fixed number of columns for each row, and a jagged a
ay is one which
has variable number of columns for each row.
• In C++, although to create a 2d a
ay/jagged a
ay you don’t need dynamic allocation, you’ll
need it to return the a
ays from a function. Therefore, I’ll discuss the dynamic allocation
version. To create a 2d a
ay/jagged a
ay A that has r rows, the syntax is int **A = new
int*[r]. To allocate c columns for row index i, the syntax is A[i] = new int[c]. Following is
a code to return a jagged-a
ay having numRows rows and numCols columns in each row.
3
int **jagged(int numRows, int *numCols) {
int **C = new int*[numRows];
for (int i = 0; i < numRows; i++)
C[i] = new int[numCols[i]];
eturn C;
}
• In JAVA and C#, to create a 2d a
ay/jagged a
ay A that has r rows, the syntax is
int[ ][ ] A = new int[r][ ]. To allocate c columns for row index i, the syntax is A[i] = new
int[c].1 Following is a code to return a jagged-a
ay having numRows rows and numCols
columns in each row.
int[][] jagged(int numRows, int[] numCols) {
int[][] C = new int[numRows][];
for (int i = 0; i < numRows; i++)
C[i] = new int[numCols[i]];
eturn C;
}
1.4 Dynamic A
ays
Here, you will use C++/Java/C# implementations of dynamic a
ays, which are named respectively
vector, A
ayList, and List.
• In C++, the syntax to create is vector〈int〉 name.
To add a number (say 15) at the end of the vector, the syntax is name.push back(15).
To remove the last number, the syntax is name.pop back().
To access the number at an index (say 4), the syntax is name.at(4).
To find the length, the syntax is name.size().
• In Java, the syntax to create is A
ayList〈Integer〉 name = new A
ayList〈Integer〉().
To add a number (say 15) at the end of the a
ay list, the syntax is name.add(15).
To remove the last number, the syntax is name.remove(name.size() - 1).
To access the number at an index (say 4), the syntax is name.get(4).
To find the length, the syntax is name.size().
• In C#, the syntax to create is List〈int〉 name = new List〈int〉().
To add a number (say 15) at the end of the vector, the syntax is name.Add(15).
To remove the last number, the syntax is name.RemoveAt(name.Count - 1).
To access the number at an index (say 4), the syntax is name[4].
To find the length, the syntax is name.Count.
1 For 2d a
ays, you could use: int A[ ][ ] = new int[r][c] in JAVA and int[ , ] A = new int[r,c] in C#
4
1.5 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
a two-dimensional jagged a
ay adjList (called adjacency list) to represent the graph. Specifically,
ow index i in the a
ay co
esponds to the vertex vi, i.e., row 0 co
esponds to v0, row 1 co
esponds
to v1, and so on. Each cell in row i stores an outgoing edge of the vertex vi. Each edge has 3
properties – src, dest, and weight, which are respectively the vertex from which the edge originates,
the vertex where the edge leads to, and the edge weight. To get the number of outgoing edges of
the vertex vi, we simply get the length of the row at index i.
In a nutshell, Edge is a class which has three integer variables – src, dest, and weight. The
adjacency list, therefore, is a jagged a
ay, whose type is Edge. In C++, we implement adjList as
a vector of Edge vectors. In Java, we implement adjList as an A
ayList of Edge A
ayLists. In
Java, we implement adjList as a List of Edge Lists.
1.6 Implementing Queue
Here, you will use C++/Java/C# implementations of the queue data structure.
• In C++, to create an integer queue, the syntax is queue
nameOfQueue
To get the size of the queue, the syntax is nameOfQueue.size()
To enqueue, the syntax is nameOfQueue.push(15)
To dequeue, use nameOfQueue.front() to get the first number and then use nameOfList.pop()
to remove it.
• In Java, to create an integer queue, the syntax is Queue nameOfQueue = new
LinkedList()
To get the size of the queue, the syntax is nameOfQueue.size()
To enqueue, the syntax is nameOfQueue.add(15)
To dequeue, use nameOfQueue.poll()
• In Java, to create an integer queue, the syntax is Queue nameOfQueue = new Queue()
To get the size of the queue, the syntax is nameOfQueue.Count
To enqueue, the syntax is nameOfQueue.Enqueue(15)
To dequeue, the syntax is nameOfQueue.Dequeue()
2 Dijkstra (10 points free – yeah I am feeling generous!)
You must have already implemented Dijkstra’s algorithm in COMPSCI 223: Data Structures; so,
we are not doing it again. Instead, you will just run the code on the US road network.
Start by downloading the large graph data from the RoadNetworks folder and appropriately
set the DIJKSTRA FOLDER variable in TestTime file.2 Then, run the TestTime code on these
networks. Look at the code and the numbers you obtained from the code. You should be able to
answer the following questions (no need to submit anything):
• What is the complexity of the Dijkstra’s algorithm implementation in this assignment?
2 Original data from http:
users.diag.uniroma1.it/challenge9/download.shtml.
5
http:
users.diag.uniroma1.it/challenge9/download.shtml
• Analyze the output of TestTime in accordance with the complexity above.3 In particular, do
the following:
– Check the DijkstraPlot excel sheet provided to you. The number of vertices and edges
are provided in columns C and D for each of the states. Write the formula for the
complexity in column E. In particular, if you have claimed that the complexity in the
previous question is O(M2), then formula in cell E5 = D5 ∗D5.
– Plot the times that you get or each of the states in the cells E20 through E29
– Once you fill in the formula/numbers in the columns above, you should obtain two
graphs. Do they look similar or different?
Please do not upload the large data files to Canvas.
Here’s what my plots look like. They are extremely similar to each other giving a strong
indication that my implementation is aligned with the theoretical bound.
3 Single Source Longest Paths in a DAG
In the lecture notes, you have seen how to compute the shortest paths in a DAG after its topological
order has been found. We remarked that the shortest path algorithm can be easily modified to
find longest paths. Here, we will implement the same; moreover, we will find longest paths and
compute topological order at the same time. See the pseudo-code in the next page.
3 The files are small enough so that the code can completely run, but if for some reason, your computer is unable
to handle all the files, then go as far as you can.
6
A Remark about Implementation: Note that we are setting the dist a
ay entries to very
small values (INT MIN for C++, Integer.MIN V ALUE for Java, and INT32.MinV alue fo
C#) to simulate −∞. Let us assume that we have a graph
v0 → v1 ← v2
where the edge weight from v0 to v1 is 5 and the edge weight from v2 to v1 is −5. A topological
order is v0, v2, v1. If we compute the longest path from v0, initially distance[1] would be set to
distance[1] = distance[0] + 5 = 0 + 5 = 5
Now on processing v2, we will compute (distance[2]− 5), which will be a large positive numbe
due to rounding of numbers. This will lead to distance[1] being e
oneously set to a positive numbe
larger than 5 (which is inco
ect as there is no way to reach v2 from v0).
Hence, if distance of the dequeued vertex equals −∞, we simply skip the remaining code inside
the outer for-loop.
Complete the longestPaths method in the DAG class using the following steps:
• Allocate numV ertices cells for the topoOrder[ ], distance[ ], and inDegree[ ] a
ays.
• Use a loop to initialize all cells of inDegree[ ] to 0 and all cells of distance[ ] to −∞
In C++, use INT MIN for −∞. In Java, use Integer.MIN VALUE for −∞. In C#,
use Int32.MinValue for −∞.
• for (i = 0 to i < numV ertices), do the following:
– for each outgoing edge adjEdge of the vertex i, do the following a
∗ increment inDegree[adjEdge′s destination] by 1
• Create an integer queue vertexQ
• for (i = 0 to i < numV ertices), do the following:
– if (inDegree[i] equals 0), enqueue i into the vertexQ
• Set distance[s] = 0 and initialize an integer variable topoLevel = 0
• while (vertexQ′s size > 0), do the following:
– let v be the vertex obtained by dequeueing vertexQ
– assign topoOrder[topoLevel] = v
– increment topoLevel by 1
– for each outgoing edge adjEdge of the vertex v, do the following:
∗ let adjV ertex be the destination of adjEdge
∗ decrement inDegree[adjV ertex] by 1
∗ if (inDegree[adjV ertex] equals 0), then enqueue adjV ertex to vertexQ
∗ if (distance[v] 6= −∞), do the following:
· let len = distance[v]+ weight of adjEdge
· if (len > distance[adjV ertex]), set distance[adjV ertex] = len
a Check the code in Dijkstra to see how one can get the outgoing edges of a vertex.
7
4 Bellman-Ford
Complete the execute method in the BellmanFord class using the following steps: