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:
| 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.
### 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 to a new vertex. Steps: 1. Start with an arbitrary vertex and add it to the MST. 2. Use a priority queue to store edges connected to the MST. 3. Extract the smallest edge from _____ ____ ______ ______ ______ ___ _____ ____ ________ _____ __________.
__________ ___ _____ __________ _______ _______ ____ ______ _______ __________ _________.
__________ ____ _____ __________ _______ ___ _________.
___ ________ _____ ___ ______ ___ ____ __________ ________ ______ ___.
______ ______ ______ ________ __________ _____ ________ ______ ________.
_______ ____ _________ _____ _________ _________ __________.
__________ __________ ___ _____ ____ ______ ____.
______ __________ _________ _________ __________ ____ __________.
________ __________ ___ ____ __________ ________.
__________ __________ ______ ____ ________ _____.
_____ _______ ___ _____ __________ _______ _________ ____ _______.
___ __________ _________ _________ __________ __________ _____ ________ _______ ____ _________.
__________ ______ ______ _____ __________ ___ ___ _________ _______.
___ _______ ____ _________ _______.
_______ ______ __________ _________ ________ _________.
__________ ____ ________ ________ ______ ________ ____ ___ _________.
________ ___ _________ __________ _____ ___ _____ ____ ____ ____ _________.
_________ __________ ______ ________ ___ ______ __________ __________ ___.
_________ ____ __________ ______ ____ _________ _______ ________ ______ ___.
________ _____ _____ _______ ________ _____ ___ ____ __________ __________.
________ _______ _________ _______ ________ ____ _____ _______.
____ ___ ________ ________ ________ _______ ___.
____ ______ ____ __________ _________ _________ _____ _____.
________ ______ _________ __________ _________.
____ ________ ______ ___ ____ _______ ______ _________ _____ __________ ______ ___.
_____ ____ _________ ___ _______ __________ __________ ________ ___ __________ _____ ______.
___ ______ ___ __________ _____ _________ ________ ________ ______ ________ __________ ________.
__________ __________ __________ ___ __________ ________ _______ ____ ________ _________ _______.
___ __________ _______ ________ ______ ___ ________.
_________ ___ _____ ________ ______ ____ _____ ________ ________ ___.
__________ _________ _________ _________ ______ __________ ____ ___ ________ __________ ______ ____.
_________ __________ ______ _______ ____ ___ ____ _________ __________.
______ ______ ______ _____ _____ _______ ____ __________ _________ ______ ________ ________.
__________ __________ ______ ____ _________ ____ ____ _________.
____ ______ _______ ______ ___ _________ _____ ______ __________ _____.
__________ ______ ____ ___ ____ ___.
______ __________ ____ ___ _____ _____ ______ ______ ___ ______.
_______ __________ _______ _________ ____ ___.
______ ________ ________ ______ ____ _________ ___.
______ ______ ________ _____ _______ _________ _______ ________ __________.
________ __________ ____ _______ ________ __________ ______ ___ ____ ______ _____.
__________ _______ ____ ________ _________ ________ ________ _______ _____ ______ ______ ______.
____ ______ ______ ______ __________ __________ _____ _______.
_______ __________ ____ ________ ______ _______ _______ ______ __________ __________.
________ _________ ________ ____ _______ ________ ________ ___ ___.
_______ _________ _________ _______ ________ _____.
_________ _________ ______ ________ ____ ___ _____ _________.
______ ____ _______ _________ ___.
____ ____ ____ __________ ___ ___ _________ ___.
________ _______ _______ ________ ____ __________ _________ ________ __________ _______.
______ __________ ______ ___ __________.
____ ______ ______ ________ ______ ______ __________.
___ _____ _______ _____ _______ _____ _____ ________ _____ _________.
_______ _____ ________ _____ _____ _____ ___ ___.
_____ ___ _____ ________ ______ _________.
____ ________ _________ ____ _____ ______ _________.
________ ____ _________ _________ ____ ______ _________.
_____ ______ ________ _____ ______ _________.
_______ _______ ___ _____ ___.
_______ ______ ____ __________ _______.
________ ________ ________ ____ ____ ___ ______ ___ ______.
______ ______ ___ __________ ____.
______ ______ ______ ____ ____ ____ _____.
Get Full Answer on WhatsApp
What is the use of Topological sorting? Write and explain the Topological sorting algorithm. Also, compute the time complexity for the topological sorting algorithm.
Explain binary exponentiation for computing the value 519. Write the right-toleft binary exponentiation algorithm and show its working for the exponentiation 519. Also, find the worst-case complexity of this algorithm
3-CNF SAT
Differentiate between Polynomial-time and exponential-time algorithms. Give an example of one problem each for these two running times.
What is a Greedy Approach to Problem-solving? Formulate the fractional Knapsack Problem as an optimisation problem and write a greedy algorithm to solve this problem. Solve the following fractional Knapsack problem using this algorithm. Show all the steps. Suppose there is a knapsack of capacity 15 Kg and 6 items are to packed in it. The weight and profit of the items are as under:
(p1, p2,…, p6) = (3, 2, 4, 5, 1, 6)
(w1, w2,…, w6) = (2, 1, 2, 1, 5, 1)
What is the purpose of using Huffman Codes? Explain the steps of building a huffman tree. Design the Huffman codes for the following set of characters and their frequencies: a:15, e:19, s:5, d:6, f:4, g:7, h:8, t:10.
State and explain the theorems for computing the bounds O, and
Apply these theorem to find the O-notation, Ω-notation and Θ-notation for the function: