Consider the following Graph:

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:

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

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, C, 2), (C, D, 3)}
   - Adding (A, C, 4) would form a cycle, so skip it.
   - Adding (B, D, 5) would form a cycle, so skip it.

MST Edges:
____ ________ _____ _____ _________.
______ _________ ___ __________ ______ __________ _____.
__________ _______ _________ _________ _______.
__________ ______ _____ _________ ______ ________ __________ __________ ______ _______ ___ __________.
_______ ___ _______ ______ __________ ________ __________ _____ _________ _________ _____.
______ _______ ____ ________ _____ _____ __________ ______ _____ ____ ___.
_____ _______ __________ ____ ____ ___ _____ ______ _____.
_________ ____ ______ __________ ___ _________ ___ ____ ___.
________ _____ ___ ______ ______.
______ _____ ___ _____ _____ ________ _______ ___.
________ ________ ________ __________ __________ __________ ____ __________ ______ ________ _____.
_________ _________ ______ __________ ______ _____ ___ ________ _____.
__________ ______ ______ _______ ________ __________ ___ _________.
______ _______ ________ __________ __________ _______.
_________ ____ ______ ___ __________ _______ __________.
______ ___ _____ __________ __________ _________ ___ ________ _____.
___ ____ _________ ___ _________ __________ ___.
____ ________ __________ ______ __________ _________ _____.
_______ ______ ___ ___ _____ _______.
__________ _______ ___ ________ _________ _____ ______.
_______ ___ ____ ______ ____ ___.
_____ _______ ____ ___ ________ _______ ________ ______ ________ ______.
______ __________ _____ _______ _______ ____ _____ ____ ____ _______.
__________ ________ ______ ________ ___ _______ ________ ______ __________.
__________ ________ ______ _______ ____ _______.
________ ______ _______ _____ __________ _______ ________ _____ _______ ______.
________ ____ __________ _________ ___ ___ ________ _____ _________ __________ ___ ___.
___ ______ ________ ____ __________.
______ ___ __________ ___ __________ _____ _____ _______ __________ ___ ______ __________.
_____ _________ ______ ___ _______ ___.
_____ ____ _____ _________ __________.
______ ______ _______ ______ _________ ______ _______ ___ __________.
________ __________ _________ _______ _______ _______ ____ _______ ______.
_____ __________ _________ ______ _______ _______ ____.
________ ________ ________ ________ _______ ______ _________ __________ __________ _____ _____.
________ _______ ___ __________ ___ ________ __________ _____ _________ _______ __________.
___ ____ ________ ________ _________ ____ _______ ____ ______ ________.
___ ____ _________ ______ ______ _______ ________ __________ ______ _______.
__________ ________ _____ ________ _________ ___ _______ _____ _______ _____ ________.
__________ ______ __________ ______ ________ ___ _________ ______ __________ __________.
______ _______ __________ ____ __________ ____ _____ __________ __________ ___ ___.
____ ________ _______ ______ __________ _______ __________ ___ ________ _____ __________ _______.
________ _____ _____ _________ ____ ____ ______.
_____ _______ _____ ___ ________ ______ _________.
___ ______ __________ _______ ________ ________.
______ ____ ________ ___ __________ _________ ________ _______ __________ ________.
__________ _____ ________ ______ _____ ________ ____ __________ __________ _______ ______ ___.
_______ ________ _______ ________ ___ ___ _________ __________.
_________ _____ __________ ______ __________ __________ ___ _______ _________ _______ ___.
__________ ________ _____ ____ _______ _________ ___.
_____ ________ ____ ___ _____ __________ __________.
______ ______ _________ ___ _____ _______ ________ ________ _____ ___ _______ _______.
_______ __________ _________ _____ _________ ________ ____ ____ __________ _________ ___ __________.
_________ _________ _____ _______ ________ ____ ________ ___ ________.
______ _____ ___ ___ ____ ____.
______ ____ __________ ________ ____.
_____ __________ __________ _____ ________ _________ _________ ________ _________ ____ _____ _________.
__________ _____ ______ ____ ________ ____ ___.
_________ ____ ___ ______ ___ _______ _______ ______.
___ ________ _________ _________ _________ ____ __________ ________.
__________ ___ _________ _____ ____ ______ ________ ___.
_________ ______ ________ __________ _____ _______ ______.
_____ _________ ____ _______ ____.
_____ ___ ___ _____ __________ __________.
__________ _______ ________ _________ _______ ___ _________ _________ ______ __________ ________.
_______ __________ ___ ________ ____ _________ _______ ______ ___.
______ _________ __________ _________ ________.
______ ____ ______ ___ ___.
___ _______ _____ _____ ___ __________ _______ _________ ________ _____ _________.
____ ____ __________ _______ ________ _______.
_______ _________ _________ ________ ______ ___.
___ ____ ____ ________ _______ ____ _____.
___ ______ _______ _____ __________ ______ ___ ______ ________.
___ ______ ___ __________ _______ ______ ___ __________ ____ _____ ____.
___ _________ _____ ______ __________ _________.
________ ______ ______ ______ ___ ______ _____.
________ ________ ____ ____ _______ _____.
_______ __________ ___ _______ _____ __________ ________ _______.
_____ ____ ______ ___ ____ _______ _______ ___ _______ ____ __________.
___ ______ __________ ___ ________ _______.
_________ ___ __________ ____ ___ ______ _________.
_______ ________ _________ ___ _____ ____ _______ ______ _________ ______ _________ ___.
_________ ________ _______ ___ _____ _______ ___.
____ ________ _________ _____ ______ ________ ___ ________ ___ ________ __________ ______.
________ ____ ________ __________ _________ ________ ______ ______ _____ ____.
_______ ___ _____ _____ _________.
_____ _____ _______ ___ _____ ____ _________ _________ ___.
___ _______ _________ ______ __________ _________ ____ _________ ________.
__________ ___ ____ _________ ___ __________ _______ __________ ____ _______ ____ ______.
____ ________ ___ ________ ___ ________ _________ _____ __________ __________ ______.
___ _______ _________ ________ ___ _______ ______ _____ ______ ________ ______ _________.
_____ _______ ______ _______ ________ _____ _______ ________ _______ _______ __________ _______.
__________ ____ ____ ______ ______ ______ ___ __________ _____ ___ _____ __________.
____ ____ _______ __________ _________ ____ ______ ___ ________ _____.
_________ __________ ___ _____ __________.
____ ________ ___ __________ ________ __________ _________ __________ _________ _____ _______ __________.
_______ _________ ___ ___ ____ __________ _________ _______ __________ ________.
_____ ______ ____ ______ _______ _____ _________.
_________ _________ _____ __________ _______ __________ ________ _______ _________.
___.
Get Full Answer on WhatsApp