Exercise 1 40 points. Graph Algorithms
The board of this exercise has size nXm 1 n,m 500. It is guaranteed that at least one of n and m is greater than 1. Each cell on the board has a digit on it a number between 0 and 9, inclusive. Your task is to develop an algorithm to compute the minimum number of moves required to go from the topleft corner of the board to the bottomright corner. If it is not possible to go from corner to corner, your algorithm must return the integer 1. From a given cell in the board that has digit j on it, a move consist of jumping exactly j cells in one of the four cardinal directions.
Let see some examples to be sure that the exercise is clear. The figure below shows three examples of boards. For the first example i.e., subfigure with label A, the value returned by your algorithm must be 2, given that the minimum number of moves to go from the the topleft corner of the board to the bottomright corner is equal to two the orange arrows depict one of those minimum paths. For the second example i.e., subfigure with label B, your algorithm must return the integer 1, given that there is no path that connects both corners. Note that in this example, any move will locate you outside of the board. For the last example i.e., subfigure with label C, your algorithm must return the integer 6. The orange arrows show the minimum required moves to go from one corner to the other.
Your job for this part of the assignment is to complete the function minmoves, which takes an int 2darray that represents the board and returns the minimum number of moves needed to go from the the topleft corner of the board to the bottomright corner. This function is located in the java file A3Q1.
Note: main function
We have already implemented a main function to read the data from the files, and to initialize the board that the function minmoves is getting as a parameter. Please note that this function will not be graded, and it is there only to make sure that all of the Comp251 students understand the input of the problem and to test their own code.
Exercise 2 40 points. Graph Algorithms
The Canadian Grand Prix is a motor racing event held annually in Montreal. In particular, the Circuit Gilles Villeneuve, which is located in the Notre Dame Island, is the venue for the Grand Prix.This year, the grand prix will happen between June 7th and June 9th. The length of the circuit is 4361 km and Valtterie Bottas has the lap record with a time of 1:13.07. The city council of Montreal is very worried about the event because it has caused a lot of trac prob lemsjams in the past. Then, for this year event, they are planning to make some changes to the trac routes going to and from the Circuit. In particular, the council is planing to change the direction of some streets to facilitate the circulation of cars during the event. The new changes must make easier for people to arrive to the circuit before the race and leave the circuit after the race. The council is aware that they need to carefully analyzeplan the changes because the changes can produce unexpected eects and they do not want to make people frustrated because they can lose votes in the next elections. There are two issues that they need to avoid.
Note: Please notice that on March 29th, we swapped the order of the items. Please refer to the post514 for more information.
1. There are points in the city i.e., metro stations, bus stations, parking spots etc from which the Notre Dame Island cannot be reached.
2. There are points in the city i.e., metro stations, bus stations, parking spots etc that cannot be reached from the Notre Dame Island.
The city council has already created dierent proposals about the changes. These proposals containrepresent a full description of how the Montreal streets will connect to each other and the Notre Dame Island the day of the race. Furthermore, the council has identified a total of up to 1000 important points that they will consider in the analysis i.e., 0 points 1000. Each interesting point is then represented by an integer id number 0 id 1000. The Notre Dame Island point is always represented by the id number 0. Given that not all the points are equally important e.g., given its high connectivity, the station BerriUqam could be considered as being more important than the Acadie station, the city is also giving you the order on which the problems with streets must be reported.
The city council knows that Comp251 students are very good in algorithms and willing to learn. Then, you have been commissioned to write a correct and ecient java code to report the list of points that have problems regarding the two issues that the city council wants to avoid as defined above.
Note: java file
Please notice that the city description will be modelled by the class Graph located in the
file A3Q2.java.
numnodes represent the number of vertices i.e., interesting points.
adj is the Adjacency List representation of the proposal i.e., graph as seen in class. order is the order on which you must report the possible problems.
issue1 is the list of interesting points that presents the issue 1.
issue2 is the list of interesting points that presents the issue 2.
There are some helper public functions already created. Please feel free to create new helper functions if needed, but please do not change the functions that have already been provided.
The task for this question of the assignment is to code the function F1, which is in charge of populating the lists issue1 and issue2 in the order defined by order.
We have already implemented a main function to read the data from the files that were provided by the city council, and to initialize the graph that models the city proposal. Please note that this function will not be graded, and it is there only to make sure that all of the Comp251 students understand the input of the problem and to test their own code.
Exercise 3 60 points. Graph Algorithms
The following is a real world problem that all parents who buy legos for their kids suer from. Kids build legos to later take apart all the pieces. The reality is that all the dierent legos that you bought one day end in a huge box containing all the pieces of legos. The problem arises when kids want to build a lego again. In particular, kids have the building instructions, but they need to look for the pieces in the huge box making the lego building process super inecient. Today, we will find a solution to this terrible problem aecting so many parents around the world. Specifically, given the instructions to build a lego toy, we want an algorithm to extract before starting the construction all the lego pieces, from the huge box, that we would need to finish the assembly of our toy.
As you may know did you play with legos?, some complex lego modules can be created by combining simpler module ones. As it turns out, some of those simpler modules might also be built with even simpler modules and so on. For example, to build 2 legoarms of a robot, we need 2 legohands. To build each legohand, we would need 5 legofingers. To build each legofinger, we need 3 legophalanx. Then, our total list of modules to build the arms of our robot would be 2 legoarms, 2 legohands, 10 legofingers, and 30 legophalanx. Given how many of some modules the kid needs the legoarm in our example, please help me to find out how many of the other simpler modules legohands, legofingers, and legophalanx in our example would we need to build them.
For this question, you will need to complete the function numpieces which receives as param
eters an array of long numbers called pieces, and a 2D array of integers called instructions.
The array pieces stores the amount of each lego module we need to built our toy. In particu
lar, the integer ai stored at the index i, specifies the amount of the ith module we need, where
0 ai 3. The size N of the array pieces is between the following limits 2 N 50. The
array instructions has dimensions M 3 and it stores all the module dependencies. The limits
for M are as follows: N 1 M N N 1 . Each row of the array instructions stores three 2
integers i.e., u, v, and w, stored in columns 1, 2, and 3, respectively that indicates that there is an instruction that takes w quantities of module u to produce one material v. You can safely assume that there will never be any cycles in the building instructions. The limits for u, v, and w are as follows: 0 u,v N, and 0 w 3. The output of the functionnumpiecesmust be an Nlength array storing the amount of modules needed to build the toy.
Lets see now an example to make sure that the task is clear. Please consider the following arrays.
numpieces 0,0,0,0,3
instructions 0,1,3, 1,4,1, 2,4,1, 3,4,2
From those arrays we can extract the following information: From the numpieces array:
We need to build 5 modules i.e., the length of the array numpieces to assemble our toy. Initially, we know that we would need 3 times the module 4 i.e., because the 3 stored in the index 4 of the array numpieces.
From the instructions array:
We need 3 modules 0 to build the module 1 i.e., first row of the array instructions. We need 1 module 1 to build the module 4 i.e., second row of the array instructions. We need 1 module 2 to build the module 4 i.e., third row of the array instructions. We need 2 modules 3 to build the module 4 i.e., fourth row of the array instructions.
We can now update the information of numpieces to reflect the total number of modules that we will need to build our toy.
For module 4.
As stated in the definition of the problem, we need 3 modules 4 to complete the toy.
For module 3.
As stated by the instructions array, we need 2 modules 3 to build one module 4. We
need to build 3 modules 4, then, we will need 6 modules 3 to complete the toy. For module 2.
As stated by the instructions array, we need 1 module 2 to build one module 4. We need to build 3 modules 4, then, we will need 3 modules 2 to complete the toy.
For module 1.
As stated by the instructions array, we need 1 module 1 to build one module 4. We
need to build 3 modules 4, then, we will need 3 modules 1 to complete the toy. For module 0.
As stated by the instructions array, we need 3 module 0 to build one module 1. And we already know that we need 3 modules 1 to complete the toy. Then, we will need 9 modules 0 to complete the toy.
Based on the abovementioned information, the array that must return your function is as follows:
numpieces 9,3,3,6,3
Exercise 4 60 points. Flow Network
In this exercise, we will implement the FordFulkerson algorithm to calculate the Maximum Flow of a directed weighted graph. Here, you will use the files WGraph.java and FordFulkerson.java, which are available on MyCourses. Your role will be to complete two methods in the template FordFulkerson.java.
The file WGraph.java implements two classes WGraph and Edge. An Edge object stores all infor mations about edges i.e. the two vertices and the weight of the edge, which are used to build graphs.
The class WGraph has two constructors WGraph and WGraphString file. The first one creates an empty graph and the second uses a file to initialize a graph. Graphs are encoded using the following format: the first line corresponds to two integers, separated by one space, that repre sent the source and the destination nodes.The second line of this file is a single integer n that indicates the number of nodes in the graph. Each vertex is labelled with a number in 0, . . . , n 1, and each integer in 0, . . . , n 1 represents one and only one vertex. The following lines respect the syntax n1 n2 w, where n1 and n2 are integers representing the nodes connected by an edge, and w the weight of this edge. n1,n2, and w must be separated by spaces. It includes setter and getter methods for the Edges and the parameters source and destination. There is also a constructor that will allow the creation of a graph cloning a WGraph object. An example of such file can be found on MyCourses in the file ff2.txt. These files will be used as an input in the program FordFulkerson.java to initialize the graphs. This graph corresponds to the same graph depicted in CLRS2009 page 727.
Your task will be to complete the two static methods fordfulkersonInteger source, Integer destination, WGraph graph, String filePath and pathDFSInteger source, Integer destination, WGraph graph. The second method pathDFS finds a path via Depth First Search DFS between the nodes source and destination in the graph. You must return an Ar rayList of Integers with the list of unique nodes belonging to the path found by the DFS. The first element in the list must correspond to the source node, the second element in the list must be the second node in the path, and so on until the last element i.e., the destination node is stored. The method fordfulkerson must compute an integer corresponding to the max flow of the graph, as well as the graph encoding the assignment associated with this max flow.
Once completed, compile all the java files and run the command line java FordFulkerson ff2.txt. Your program will output a String containing the relevant information. An exam ple of the expected output is available in the file ff2testout.txt. This output keeps the same format than the file used to build the graph; the only dierence is that the first line now represents the maximum flow instead of the source and destination nodes. The other lines represent the same graph with the weights updated to the values that allow the maximum flow. There are a few other open test cases you can access on EdLessons. You are invited to run other examples of your own to verify that your program is correct. There are namely some examples in the textbook.
What To Submit?
Attached to this assignment are java template files. You have to submit only this java files. Please DO NOT zip or rar your files, and do not submit any other files.