IGNOU MCS 211 2026 - Explain the divide and conquer approach of multiplying two large

Question

Explain the divide and conquer approach of multiplying two large matrices of size 16 x 16. Compute the time complexity of this approach.

Consider the following Graph:

Image ignouacademy-com--p-conquer-27601

Figure 1: A sample weighted Grари

a) Write the Kruskal's algorithm to find the minimum cost spanning tree of a graph. Also, find the time complexity of Kruskal's algorithm. Demonstrate the use of Kruskal's algorithm and Prim's algorithm to find the minimum cost spanning tree for the Graph given in Figure 1. Show all the steps.

Bellman-Ford's shortest path algorithm for the graph given in Figure 1. Show all the steps of computation.

search (where pi represents the probability that the search will be for the key node ki, whereas qi represents that the search is for dummy node di. Make suitable assumptions, if any)

18 Feb 2026

Answer :

Word Count : 686

The divide and conquer approach for multiplying two large matrices of size 16x16 involves breaking down the problem into smaller subproblems. To multiply two matrices, A (of size 16x16) and B (of size 16x16), we divide each matrix into four submatrices. Each matrix is split into 4 submatrices, resulting in submatrices A1, A2, A3, A4 for matrix A and B1, B2, B3, B4 for matrix B. We then perform recursive multiplications of these smaller submatrices. The multiplication of matrices is done in a way that reduces the overall computational complexity by solving subproblems recursively. For matrix multiplication, we use the Strassen algorithm. This algorithm divides each matrix into 4 blocks (submatrices) and recursively computes the matrix product. Instead of performing the multiplication of submatrices directly, it computes 7 products of submatrices using additions and subtractions, which is fewer than the usual 8 multiplications. This reduces the time complexity. The time complexity of the traditional matrix multiplication approach is O(n^3), where n is the size of the matrix. However, with the divide and conquer approach using Strassen’s algorithm, the time complexity is reduced to O(n^log2(7)), which is approximately O(n^2.81). --- Kruskal's algorithm is used to find the minimum cost spanning tree (MST) of a graph. The algorithm follows these steps: 1. Sort all edges in the graph by their weight. 2. Initialize a forest, where each node is its own tree. 3. Process the edges in sorted order and add the edge to the MST if it does not form a cycle with the edges

_______ _____ ___ _____ ___ _____ ___ _____ ___.
_____ ________ _______ _____ _____ ______ _______ ________ ______ _________ _______ ______.
____ _________ ________ __________ __________ _________ _________ _____ ___ ____ __________ _________.
___ ____ ________ _______ ____ ________.
________ ________ __________ __________ _____ ___ __________ ____.
________ ______ ___ _____ ________ ________ ____ _________ ___.
_______ ____ ______ _____ ____ ___ _________ __________ ______ _____ _____.
_____ ________ ________ ________ ____ _________ _____ _________ __________ ___ _____ __________.
_______ ______ _______ ___ ____ _______ ________ __________.
_______ _____ ____ ______ ________ __________ __________ _____ ________.
____ _____ ______ _____ ______ ______ ___ ______ _________ __________.
__________ ____ _____ _________ ______ ____ _________ __________ ________ _______ ____ _________.
___ _____ ________ ___ ___ __________ _________ __________ ____ __________ ___ _______.
________ ________ ____ ____ ___ ______.
___ ________ ________ ___ ______ ________.
__________ __________ ______ __________ ________ ______ _______ ______ ________.
_____ _______ ____ ________ ________ ___ _____.
___ ________ __________ ______ _______ ___.
________ _______ ____ ______ __________ ___ _____.
_____ _____ _____ ________ ________ _________ ___ ________ ______ _____.
_________ _________ ________ _____ _________ ____ ______ _________ __________ ___ ______ _______.
_____ _____ ________ ____ __________.
________ ______ ________ __________ __________ ______ ____ ___ __________.
_______ __________ ____ __________ ___ _________ ________ __________ ______ ___ ________ ________.
____ ______ ____ ____ _______ ___ ______ ___ ____ _____ ________.
_________ ______ ________ ___ ____ _________ _____ ______ __________ _____ ___.
_____ _______ __________ __________ _______ _________.
______ ____ _______ ___ ___ ______ ________ _________.
__________ _____ _______ _______ _____ ________ ________ ____ ___ _______.
_________ ____ _____ _________ ______ __________ _____ ___ __________ ________ ______ _______.
_______ _____ _______ ______ _______.
_________ ___ ___ _________ ___ _______ ______.
________ _____ ___ __________ ________ _______ ________ ___ _______ _________ ___ _____.
_______ ___ ___ ______ _________ ____ _____ ________.
________ ___ _____ ________ ________ _________.
____ ______ _____ ______ _______ ___ ___ _________ ________ ______ __________.
________ ____ ___ ____ _______ ______.
________ ________ ______ ____ _____ ____ __________ ________.
________ _____ ________ ____ ______ __________ _________ _________ __________.
________ ______ ___ __________ ___ _____.
________ _____ ______ ______ ________ ____ ________ ______ __________.
_____ _______ ___ __________ ______ _____ __________.
______ __________ _____ _________ _____ ____ _________ ________ __________ ______ __________.
_________ ___ _______ ____ _______ ___.
_______ _____ ________ _________ __________.
_______ ___ _____ ___ ______ ________ _________ _______.
__________ ______ ________ ____ __________ ____ _______ ________ ______ _______ _______.
____ __________ _______ _____ __________.
____ _______ _________ ________ ______ _______ ________ ______ _____ ______.
_________ ______ ____ _______ ________.

IGNOU ACADEMY

Your IGNOU journey, made easier.

Solved Assignments
Study Notes
Guess Papers
Question Papers

Call Us WhatsApp

STUDY • PREPARE • SUCCEED

Skip in 10

IGNOU Solved Assignments Assignments Ignou Projects Project Previous Year Solved Exam Papers Notes Notes Sample Question Papers Sample Question Papers