Question

Consider the following Graph:

Image ignouassignments-ignouacademy-com--p-following-45695

Figure 1: Graph for Problem 3(a) and 3(b)

a) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost
spanning tree of the graph given in Figure 1. Show all the steps of computation.
Also, compute the time complexity of both the algorithms.
b) In the Figure 1, find the shortest path from the vertex ‘a’ using Dijkstra’s shortest
path algorithm. Show all the steps of computation. Also, find the time complexity
of the algorithm.
c) What is dynamic programming? What is the principle of Optimality? Use the
dynamic programming approach to find the optimal sequence of chain
multiplication of the following matrices:

Matrix Dimension
A1 5 x 10
A2 10 x 20
A3 20 x 15
A4 15 x 8
A5 8 x 10

d) Make all the possible Binary Search Trees for the key values 25, 50, 75.
e) Explain the Knuth Morris Pratt algorithm for string matching. Use this algorithm
to find a pattern “algo” in the Text “From algae to algorithms”. Show all the steps.
What is the time complexity of this algorithm

25 Jul 2024
Answer :
Word Count : 1061

Sure, let’s break down each part of your question step-by-step.

### a) Minimum Cost Spanning Tree Algorithms: Kruskal’s and Prim’s

#### Kruskal’s Algorithm:

Kruskal’s algorithm builds the Minimum Spanning Tree (MST) by adding edges one by one in increasing order of weight, ensuring no cycles are formed. 

Steps:
1. Sort all edges in the graph in non-decreasing order of their weights.
2. Initialize an empty forest, where each node is a separate tree.
3. Add edges to the forest by picking the smallest edge. Only add an edge if it doesn’t form a cycle with the already chosen edges. To check this, use a Union-Find data structure.

Example:
1. Sort edges: (A, B, 1), (B, C, 2), (C, D, 3), (A, C, 4), (B, D, 5)
2. Initialize empty forest.
3. Add edges:
   - (A, B, 1) → MST: {(A, B, 1)}
   - (B, C, 2) → MST: {(A, B, 1), (B, C, 2)}
   - (C, D, 3) → MST: {(A, B, 1), (B, ________ ___ _______ __________ ____ _____.
____ ________ ___ ___ _______ ______.
________ _________ _______ __________ ______ ______.
_______ _______ _______ _____ ____ _________ __________ _____.
_____ _______ ______ _______ _______ ____ ___ ___.
__________ ____ __________ _________ ______ __________ __________.
_____ ______ ____ ________ __________ ______ ______ _______ __________.
________ ________ _________ _______ ______ _________.
___ _________ ________ _________ _________ ____ ______ ______ ___ _________.
_______ _______ __________ ________ _________ ______ _________ ________ ________.
___ _______ ____ ____ _______ ______ __________.
____ _____ ____ _____ ____.
__________ ________ _________ _______ _________ _______ _____ ____ __________ _______ _________ __________.
_________ ____ _____ _____ _______ _______ __________ ____ ____.
_______ _________ ______ ____ ____ __________ _________.
____ _________ _________ _____ ___ ____.
___ _________ ________ ____ __________ ________ ______ ____ _____ _______ ____.
________ ________ _______ _______ ________ _________ ___ ____ ______.
___ _________ ______ ______ _________ __________.
____ ________ ________ __________ _______ _______ _______ ____ _____ ______ ______.
_______ ____ ___ __________ ______ ______.
_____ _____ _______ ____ ___.
_______ _________ ___ ________ ___.
____ ____ ______ ___ _________ _________ ________ _____ ____ ______.
____ _______ _______ ______ ____.
____ __________ __________ _____ ________ _____ _______ ________ __________ ________ ___.
_____ _______ _____ ____ __________ _______ _________ ______ ______.
_______ ______ __________ _________ ___ _____ ________.
_________ _____ __________ ___ __________.
__________ ________ ________ ______ _______ ____ ________ __________ ____ ____ ____.
_______ ____ ________ ______ ______ ____ _________ _______ _______ _________ ___ ____.
__________ ___ _________ ________ ____ _____ ____.
______ ______ _________ ___ __________ ___ ______.
___ ________ ______ ______ ________.
_____ _____ __________ _______ ___.
_________ ______ ____ ____ ________ _______ _____ _____ _______ ___ ___.
__________ ___ __________ _________ ________ _________ ______ ________ _________ _________ _______.
______ __________ __________ ___ ____ ________ ____.
________ ______ ________ _______ ___ ___ __________ _________ ___ _______ _______.
________ _____ ________ _________ _________ ____ ______.
_____ __________ ____ _______ _____ ____ ____ ___ __________ ______.
___ ____ ___ _________ _____ _________ ______.
________ ___ ____ _________ __________ _______ _________ _________ _______.
__________ ___ _________ ____ ___ ________ ___ ____ _________ _________ _____ ____.
______ _________ ___ __________ ________ ___ _______ _____ ____.
______ _______ _______ ________ _______ _____ __________ _______ __________ _______.
___ ________ _______ __________ _____.
__________ ____ __________ _______ _____ __________ ______ __________.
_________ ___ ___ ____ __________ _________ _______ __________.
______ ___ _______ ______ ________ _____ ____ ______ _________.
_____ _________ _________ _____ _____ _______.
______ _____ _____ _____ ___ ______ _____ ________ __________ ______ ___.
________ ______ __________ ______ _____ _______ ______ ______ _____.
____ ____ ______ __________ ________ _______ ____ ______.
_________ _______ ___ __________ _____.
_____ ____ __________ _____ ______.
_________ _________ _________ _________ _________ __________ ______.
___ _______ ___ _________ _______.
_____ _________ __________ _____ ________.
___ ______ ________ ________ ________ ____.
__________ _____ _______ ________ ___ __________ _________ ___ ______.
____ _______ _________ __________ _________ _______ _________ _____ ______ ___ _______ ______.
________ ________ ______ __________ ____ _____ _________ ___ _____ ______ ________ ______.
________ _____ _____ _____ ____.
______ __________ _____ ________ ___ _________ _________ _____ _______.
__________ _________ _______ ____ ___.
______ _______ ____ ________ ____ ______ ________ ______.
_______ _____ _______ ___ ____ ______.
_________ __________ _______ ______ _________ _______ ______ _____ __________ _________.
_________ _________ _________ ______ __________ ___ ____ _______ __________ _________.
____ ____ ________ __________ ____ ______ _____ ____.
_________ _____ __________ ___ _______ ______ _____.
___ ______ ________ ___ _________ _______ _____.
_________ _____ _____ _____ _____ ___ _______ _______ ______ _________ ______.
______ ____ ____ _____ ______ ________ _________ _______ _________ ___.
______ ___ ________ _________ ___.
_______ __________ _______ _________ _____ _____.
__________ ___ ________ __________ _____ ____ _______ __________.
___ _________ __________ ____ ____ ____ _______ ________ _____ _______ ________ _________.
______ _________ _____ _________ _____ ___.
________ _________ _______ __________ ______ ____ _______ ____ ______ ______ ________.
___ ____ _____ _______ _________ ________ _____ ____.
_________ _________ ________ _______ _____ ___ _______ _____ _________ _________ _____.
__________ _______ ___ _____ _____ __________ __________ ___.
____ ___ _____ ________ __________ ______.
_____ __________ _____ __________ ____ _________ __________ ____.
_________ ____ _________ ____ _______ _________.
_________ _________ ________ ____ ___.
________ ____ ___ _________ ________ ______.
_________ _____ _____ ___ _______ ________ ____ ____ ____.
_____ _________ _____ _______ ___ ______.
__________ ___ __________ _____ _______ _____ _______ _________ _____ _________.
_____ _______ _________ __________ ______ _________ _______ ___.
_________ _______ __________ _________ ______ _______ ____ ___ __________ _____ __________.
__________ _________ ____ _______ _____ __________ ________ _____ _____ ____ ____.
___ _____ __________ _____ __________ __________ __________ _________ _________ _____ ________ _________.
____ ______ ____ _________ _____ ____ _____ ______ _________ ____ _____ ______.
__________ ___ _______ _____ ______ __________ ________ _______.
_______ __________ ______ ____ _________ ________.
______ ____ ______ _____ ___ ____ ____ ___ ________ __________ ______.
__________ _________ __________ _____ _______ ___ ________ ______ ______ ___ _________.
__________ __________ _________ _________ __________ _____ _____ ________ ___ _______.
_______ ______ _______ _____ ______ _________ _______.
_____ ___ ______ __________ _____ ____ ___ ________ _______ ___.
_______ _______ ____ ____ ________ ___ ______ _____ ___.
_______ ___ _________ ___ ______ _____.
____ _________ _____ ____ _______ __________ _____ _________ _____.
________ __________ ________ ______ _____ _______.
_________ ___ _______ ___ _________ __________.
___ __________ ________.
Get Full Answer on WhatsApp

IGNOU NEWS
Assignment Submission Last Date Extended Till 30 June 2026 Click Here★★★IGNOU June 2026 TEE Date Sheet Released Click Here★★★
Top
📞
Call Support Instant phone assistance Consider the following Graph:Figure 1: Graph for Problem 3(a)
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→