Hey anyone please help me out with these tasks. Please do the complete parts of the problem. I will be very thankful to you.

Here is the problem:

Problem 5-2 (*APSP)

Let G = (V, E) be an undirected, unweighted, connected, n-vertex graph, represented by an adjacency matrix A[1..n, 1..n]. In this problem, we will derive a sub-cubic algorithm to compute the n × n matrix D[1..n, 1..n] of shortest-path distances in G using fast matrix multiplication. Assume that we have a subroutine MatrixMultiply that computes the standard product of two n × n matrices in O(n ω ) time, for some constant 2 ≤ ω < 3.

1. Let G2 denote the graph with the same vertices as G, where two vertices are connected by a edge if and only if they are connected by a path of length at most 2 in G. Describe an algorithm to compute the adjacency matrix of G2 using a single call to MatrixMultiply and O(n^2 ) additional time.
2. Suppose we discover that G2 is a complete graph. Describe an algorithm to compute the matrix D of shortest path distances in G in O(n^2 ) additional time.
3. Suppose we recursively compute the matrix D2 of shortest-path distances in G2. Prove that the shortest-path distance in G from node i to node j is either 2 ∗ D2[i, j] or 2 ∗ D2[i, j] − 1.
4. Now suppose G2 is not a complete graph. Let X = D2 × A, and let deg(j) denote the degree of vertex j in the original graph G. Prove that the shortest-path distance from node i to node j in G is 2D2[i, j] if and only if X[i, j] ≥ D2[i, j]deg(j).
5. Describe an algorithm to compute the matrix D of shortest-path distances in G in O(n^ω log n) time.