Assignment 4 CSCE 350

Programming Assignment 4
CSCE 350 : Data Structures and Algorithms

Instructions:
• The solutions should be very clear and should follow the instructions below and the requirements
stated for each problem.
• If you refer to any resource to get your solutions, add an acknowledgement with your solutions (details
of the source, e.g., book, website, etc.).
• All the codes should be written in c or c + + or JAVA for linux and commented appropriately for
major steps/functions.
• Code that does not compile will not be graded and get a 0 automatically.
• The codes should be submitted as a single zipped file through Blackboard
Part A:
1. Implement Floyd’s Algorithm for all pairs shortest paths using C or C++ or Java. (50 pts)
ALGORITHM Floyd(W[1, . . . , n, 1, . . . , n])
D ← W
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
D[i, j] ← min{D[i, j], D[i, k] + D[k, j]}
return D
Requirements:
(a) Your code should be able to read an input ASCII file named ‘input.txt’, which contains a distance
matrix with non-negative floating-number distances and the diagonal entries are all zeros.
(b) Your code will produce an output ASCII file named ‘output.txt’, which contains the final distance
matrix for all pairs shortest paths.
(c) A script file or readme file including the instructions to compile and run the code should be
submitted together with the codes
2. Implement the M aximumBipartiteM atching(G) in Section 10.3 in your text book in C or C + +
or Java. (100 pts)
Requirements:
(a) Your code should be able to read an input ASCII file named ‘input.txt’, which contains the
vertices from set V in the first row in the form of an array separated by space, the vertices from
set V in the first row in the form of an array separated by space, and starting from third row, the
adjacency matrix is stored as a two-dimensional array.
(b) Your code will produce an output ASCII file named ‘output.txt’ containing the maximum matching of the input bipartite graph in the same format as the input.
(c) A script file or readme file including the instructions to compile and run the code should be
submitted together with the codes
1