Question

Consider the following Graph: 

Image ignouassignments-ignouacademy-com--p-graphnbsp-83851

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 × 10
  A2   10 × 20
  A3   20 × 15
  A4   15 × 8
  A5   8 × 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.

07 Mar 2024
Answer :
Word Count : 701
### a) Kruskal’s and Prim’s Algorithms for Minimum Spanning Tree (MST) #### Kruskal’s Algorithm: Kruskal’s algorithm builds the MST by sorting all the edges in the graph in increasing order of their weight and adding the smallest edge that doesn’t form a cycle. Steps: 1. Sort all edges in non-decreasing order of weight. 2. Initialize a disjoint set (Union-Find) to keep track of connected components. 3. Iterate through the sorted edges and add the edge to the MST if it doesn’t form a cycle. 4. Repeat until \(V-1\) edges are added (where \(V\) is the number of vertices). Time Complexity: - Sorting edges: \(O(E \log E)\) - Union-Find operations: \(O(E \log V)\) - Total: \(O(E \log E)\) #### Prim’s Algorithm: Prim’s algorithm builds the MST by starting from an arbitrary vertex and adding the smallest edge that connects the tree _________ _________ _______ __________ _________.
_____ __________ ________ _________ ________ ____ ______ _____ ______ ___ _________.
________ ____ ______ ____ _______ ____.
____ __________ ___ __________ ________ ___ ________ ______ __________ _____ _________.
________ ______ ___ _____ __________ __________ _____ __________.
_________ _________ ____ ______ _______ __________ ________ ______.
_______ _____ ______ ___ ___ __________ ______ __________ _________ ____.
_______ _______ _________ _________ ______ _________ ___ ________ ______.
___ _______ ____ _________ ______ __________ _____ ____ ______ ____.
__________ ___ ________ ________ __________ ____ ________ ____ ______ ____ _____.
_______ ______ _________ _______ _________ ______ ________ _______ _________.
______ ___ ________ _____ ____ _____ ___ ________.
_______ _______ ____ ________ _________.
____ ___ _____ ______ ________ ___ ___ _________ __________ _____.
________ ____ _______ _______ ______ _______ ______ ______.
___ _______ __________ ________ ______ ____ ______ _________ _______ _______ ____.
_______ ___ _________ ___ _____ _______ _______ __________ _____.
__________ _______ ________ _____ _________ ________ ______ _______ _______ _________.
_________ _____ ___ ___ __________ ___ ____ ________ __________.
________ ______ __________ ________ ________ ___ ___ _____ _________ _____ ____ _______.
__________ ____ _________ ____ ______ _____.
_____ ___ __________ ______ ____ __________ ___ _____.
_______ _______ ____ _______ _______ ________ ___ ______ _______ ___ _____ ___.
___ _________ ___ _____ ___ _________.
_________ _________ _______ ________ ________ ____ _____.
_________ ___ __________ _____ ___ ________ _______ ____ ______.
________ _______ ______ _________ _________ ___ ______ _____ ______ ______ _______.
___ ___ _____ _______ _______ _________ _________.
__________ ________ ______ _____ _________ __________ _______ ______ _______.
_____ ________ ________ ____ ____ ______ ___ _____ ______ _____ ___ ____.
__________ ___ ____ _____ ________ ____ _________ __________ ______ __________.
____ __________ ______ __________ _________ ________.
________ __________ ___ ________ _______ ______ ___ ___ ___.
_____ __________ ________ ______ ________ _____ ______ __________ ____ _____ _______ _________.
_________ ____ _____ ______ ____ __________ ________ ______ ________.
_____ _________ _________ __________ __________ _______ __________ ___ __________ _________ _________ __________.
______ ________ ________ ______ __________.
_______ __________ _________ __________ ___ ________ _____.
________ _________ ____ ___ _____ __________ ________.
_______ ___ _____ _________ ___ _________ _____ _______ ________ _______ ________.
___ _________ _____ _______ _____.
_____ _____ __________ _____ __________ ______ ____ ________ ___ ____ __________.
________ __________ ________ ______ _______ _______ ________.
____ ___ _______ ______ ___.
______ _________ __________ __________ ___ _______ ______ ________ ______ _________ ___.
___ ___ ________ ______ _______.
____ ___ ______ __________ _________ _____ __________ __________ _________ ____ ___ _____.
_________ _____ ____ ________ _________ ______ ____ _______ ________ ___ _______.
_______ _________ ____ ______ _________ ___.
________ __________ __________ _____ __________ ____ ________ _________ ____ ___.
_______ ______ _________ _______ ________ ____ ________.
_________ __________ _______ _______ __________ _____ __________ ________ ___ ___.
_______ _________ ______ ___ _____ _____ __________ ____ _________ ___ _____.
___ ______ ___ _____ ___ __________ ____ ______.
_______ ____ ____ _______ ______ _______ _________ _________.
____ __________ _________ ______ __________ ________ _____ ______ ________.
__________ ____ _____ ______ ________ _____ _________ ___.
_________ ____ _____ ________ ___ ____ ___ ___ ________ _________ _________.
__________ _____ ______ _______ ______ ____ __________ _____ _____ _______ ___.
__________ ____ ____ ________ ________ _________.
_____ ______ _________ ________ ______ ______.
__________ ______ _________ _____ ____.
__________ ____ _________ __________ ________ ___ ____ ____ _______ ____ ______.
_________ __________ _______ _______ _____ ___ ___ __________.
__________ _________ ______ _____.
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
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→