All the assignment information are in the attached pdf
Programming Assignment 4 (Longest Paths in DAG, Bellman-Ford, All-Pair Shortest Paths, Minimum Spanning Trees, and Knuth-Morris-Pratt) Department of Computer Science, University of Wisconsin – Whitewater 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 error 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 Correctness Use TestCorrectness 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 correct. Output is provided in the ExpectedOutput file. You can use www.diffchecker.com to tally the output. www.diffchecker.com To test the correctness of the longest paths algorithm, I have included 2 sample files: dag1.txt, and dag2.txt. To test the correctness of Bellman-Ford, I have included 3 sample files: bellmanford1.txt, bellmanford2.txt, and bellmanford3.txt. To test the correctness of Dijkstra, I have included 2 sample files: dijkstra1.txt, and dijkstra2.txt. To test the correctness of Johnson and Floyd-Warshall, I have included 3 sample files: apsp1.txt, apsp2.txt, and apsp3.txt. The cor- responding graphs are shown below. Each .txt file has the following format. First line contains the number of vertices and edges respectively. 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 1-10-5 -1-1 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 correctness of your MST implementations, I have included: mst graph.txt; the corre- 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; corresponding MST on right 1.2 C++ Helpful Hints Use DYNAMIC ALLOCATION for declaring any and all arrays/objects. Remember to return an array from a function, you must use dynamic allocation. So, if you want to return an array x having length 10, it must be declared as int *x = new int[10]; 1.3 Multidimensional arrays A 2d array is one which has fixed number of columns for each row, and a jagged array is one which has variable number of columns for each row. • In C++, although to create a 2d array/jagged array you don’t need dynamic allocation, you’ll need it to return the arrays from a function. Therefore, I’ll discuss the dynamic allocation version. To create a 2d array/jagged array 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-array 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]];="" return="" c;="" }="" •="" in="" java="" and="" c#,="" to="" create="" a="" 2d="" array/jagged="" array="" 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-array="" 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]];="" return="" c;="" }="" 1.4="" dynamic="" arrays="" here,="" you="" will="" use="" c++/java/c#="" implementations="" of="" dynamic="" arrays,="" which="" are="" named="" respectively="" vector,="" arraylist,="" 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="" arraylist〈integer〉="" name="new" arraylist〈integer〉().="" to="" add="" a="" number="" (say="" 15)="" at="" the="" end="" of="" the="" array="" 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="" arrays,="" 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="" array="" adjlist="" (called="" adjacency="" list)="" to="" represent="" the="" graph.="" 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="" 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="" array,="" whose="" type="" is="" edge.="" in="" c++,="" we="" implement="" adjlist="" as="" a="" vector="" of="" edge="" vectors.="" in="" java,="" we="" implement="" adjlist="" as="" an="" arraylist="" of="" edge="" arraylists.="" 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="">
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 array entries to very small values (INT MIN for C++, Integer.MIN V ALUE for Java, and INT32.MinV alue for 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 number due to rounding of numbers. This will lead to distance[1] being erroneously set to a positive number larger than 5 (which is incorrect 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[ ] arrays. • 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: