please answer all these questions $.$ for warshall give solution on paper $.$ please answer all.

Course Code: $375$

Answer all of the questions. Marks for each question is indicated on the right stde

$2.$ a$.$ How does the Floyd$-$Warshall Algorithm work? Explain using appropriate pscudo

$J$

codes.

b$.$ Consider the following graph, Apply Warshall's algorithm to find the all$-$pair shortest

$7$

path.

$2.$ a$.$ Define Minimum Spanning Tree $($MST$).$ Discuss some practical applications of MST algorithm.

b$.$ Write a well$-$known algorithm for Constructing MST$.$

$3$

$7$

$3.$ a$.$ Consider two strings "AGGTAB" and "GXTXAYB". Find the longest common subsequence in these two strings using a dynamic programming approach.

$8$

b$.$ Run the Graham scan algorithm to compute the convex hull of points below, starting from $..-.$n:n vour answer in each step.

$7$