For all of the following exercises, write a program, test and and submit the file in the web submission system. Your program should have a main function and inputs such as the path of the graph file are are passed as arguments for the main function. 1 Exercise 1 Programming Exercises 1. Implement a graph traversal algorithm (in a file called Acyclic.java) that takes a directed graph G = (V; E) as an adjacency matrix, where Gi;j 2 Z denotes an existing edge from i (in the ith row) to j (in the jth column) with weight Gi;j if it is not equal to 0. Otherwise, if the weight is 0, there is no edge from i to j. You program should find out whether the input graph is acyclic. As the output, the program should print 0 if the graph does NOT have cycles and it should print 1 otherwise. 2. Write another program (in a file Scc.java) that takes a graph as above and finds all of the strongly connected components (SCC). Your program should print the size of each SCC separated by a comma.Paper Based Questions 26666664 0 1 3 0 0 3 3 0 5 1 2 2 1 −1 0 0 2 1 1 0 1 0 5 0 0 3 1 1 0 0 2 0 0 0 2 0 37777775 Is the following statement true or false? Prove or reject by example. 2 Exercise 3 Shortest Path Algorithms 1. What happens if you use the Bellman-Ford algorithms without the post-processing part? Explain what type of inputs may cause problem and why. 2. You are developing a packet routing program for a network. To select the next server to forward a packet, you would like to choose a router that has the maximum number of shortest paths from the current router (so that you reduce the risk of the packet getting lost). Suppose you are given a network map with distance between each pair of directly connected routers. Design an O(V + E)-time algorithm that finds the number of shortest paths between the current router (the source vertex s) and the next router (the target vertex t). 3. Use a proper algorithm to find all pairs shortest paths (APSP) for the following graph and write down the final result. Exercise 4 True or False 1. Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. 2. Running Dijkstra on a graph always gives correct distances. 3. If all edges in a graph have distinct weights, then the length of the shortest path between two vertices is unique.