Ask Java Expert


Home >> Java

1. We will implement the Ford-Fulkerson algorithm to calculate the Maximum Flow of a directed weighted graph. Here, you will use the files WGraph.java and FordFulker-son.java, which are available on the course website. Your role will be to complete two methods in the template FordFulkerson.java.

The ?le WGraph.java is the similar to the file that you used in your previous assignment to build graphs. The only differences are the addition of setters and getters methods for the Edges and the addition of the parameters "source" and "destination". There is also an additional constructor that will allow the creation of a graph cloning a WGraph object. Graphs are also encoded using a similar format than the one used in the previous assignment. The only difference is that now the first line corresponds to two integers, separated by one space, that represent the "source" and the "destination" nodes. An example of such file can be found on the course website with 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 staticmethods fordfulkerson(Integer source, Integer destination, WGraph graph, String filePath) and pathDFS(Integer source, Integer destination, WGraph graph). The secondmethod pathDFS finds a path through a Depth First Search (DFS) between the nodes "source" and "destination" in the "graph". You must return an ArrayList 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 ?ow of the "graph" and the graph itself.

The method fordfulkerson has a variable called myMcGillID, which must be initialized with your McGill ID number.

Once completed, compile all the java ?les and run the command line java FordFulkerson ff2.txt. Your program must use the function writeAnswer to save your output in a ?le. An example of the expected output file is available in the file ff226000000.txt. This output keeps the same format than the file used to build the graph; the only difference is that the first line represents now the maximum flow (instead of the "source" and "destination" nodes). The other lines represent the same graph with the weights updated with the values that represent the maximum flow. The file ff226000000.txt represent the answer of the example showed in [CLRS2009] Pag 727. You are invited to run other examples of your own to verify that your program is correct.

2. We want to implement the Bellman-Ford algorithm for finding the shortest path in a graph where edge can have negative weights. This question extends the previous question on the implementation of the Dijkstra's algorithm done in the assignment 2. You will need to execute this program to use the same auxiliary class Wgraph used in question 1. Your task is to fill the method BellmanFord(WGraph g, int source) and shortestPath(int destination) in the file BellmanFord.java. The method BellmanFord takes a object WGraph named g as an input (See Assignment 2) and an integer that indicates the source of the paths. If the input graph g contains a negative cycle, then the method should through an exception. Otherwise, it will return an object BellmanFord that contains the shortest path estimates (the private array of integers distances), and for each node its predecessor in the shortest path from the source (the private array of integers predecessors).

The method shortestPath will return the list of nodes as an array of integers along the shortest path from the source to the node destination. If this path does not exists, the method should throw an exception.

Input graphs are available on the course webpage to test your program. Nonetheless, we invite you to also make your own graphs to test your program.

3. Give an O(n lg n) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers. (Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i   1. Maintain candidate subsequences by linking them through the input sequence.) We do not ask you to prove your algorithm, but a complete exact proof will receive a bonus.

4. Apply the Neddleman-Wunch algorithm to find the optimal sequence alignment between the sequences !1 = AACT and !1 = GAT. We set all the substitution, deletion and insertion costs at 1, and the match score to -1. Here, your goal will be to compute the alignment with the minimum score. Show the complete dynamic programming table filled by the algorithm, and show the path(s) corresponding to the optimal sequence alignment. Write down the alignment and its cost. (Note: Alternatively, you can choose to use the edit scores used in class and maximize the score.)

Attachment:- Assignment Files.rar

Java, Programming

  • Category:- Java
  • Reference No.:- M92250829

Have any Question?


Related Questions in Java

Chatbotscreate a small networked chat application that is

Chatbots Create a small, networked chat application that is populated by bots. Introduction On an old server park, filled with applications from the early days of the internet, a few servers still run one of the earliest ...

Assignment taskwrite a java console application that allows

Assignment task Write a java console application that allows the user to read, validate, store, display, sort and search data such as flight departure city (String), flight number (integer), flight distance (integer), fl ...

Assignment game prototypeoverviewfor this assessment task

Assignment: Game Prototype Overview For this assessment task you are expected to construct a prototype level/area as a "proof of concept" for the game that you have designed in Assignment 1. The prototype should function ...

Assignment taskwrite a java console application that allows

Assignment task Write a java console application that allows the user to read, validate, store, display, sort and search data such as flight departure city (String), flight number (integer), flight distance (integer), fl ...

In relation to javaa what is constructor the purpose of

(In relation to Java) A. What is constructor? the purpose of default constructor? B. How do you get a copy of the object but not the reference of the object? C. What are static variables and instance variables? D. Compar ...

Project descriptionwrite a java program to traverse a

Project Description: Write a java program to traverse a directory structure (DirWalker.java) of csv files that contain csv files with customer info. A simple sample in provided in with the sample code but you MUST will r ...

Fundamentals of operating systems and java

Fundamentals of Operating Systems and Java Programming Purpose of the assessment (with ULO Mapping) This assignment assesses the following Unit Learning Outcomes; students should be able to demonstrate their achievements ...

Assessment -java program using array of Assessment -JAVA Program using array of objects

Assessment -JAVA Program using array of objects Objectives This assessment item relates to the course learning outcomes as stated in the Unit Profile. Details For this assignment, you are required to develop a Windowed G ...

Applied software engineering assignment 1 -learning

Applied Software Engineering Assignment 1 - Learning outcomes - 1. Understand the notion of software engineering and why it is important. 2. Analyse the risk factors associated with phases of the software development lif ...

Retail price calculatorwrite a java program that asks the

Retail Price Calculator Write a JAVA program that asks the user to enter an item's wholesale cost and its markup percentage. It should then display the item's retail price. For example: (If an item's wholesale cost is 5. ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As