Question
Apply Prim's Algorithm to find the minimum spanning tree for the following graph.
Apply Insertion and Selection sorting algorithms to sort the following list of items. So, all Intermediate steps. Also, analyze their best, worst and average case time complexity.
12, 5, 2, 15, 25, 30, 45, 8, 17, 50, 3, 7
Answer :
Word Count : 795
________ _____ _________ ________ _________ ________ ___ ________ _____ ______ __________.
___ ________ ____ ______ ______ ____ ________ ____ ____ _______ _________.
_____ ________ _________ _________ ____ _____ ________ ___ ______ ______ _______.
____ ________ __________ ____ _________ ____ ________ ____.
________ __________ ___ __________ ____ ______ ______ ____ __________.
____ ___ _______ _____ ___.
_________ ______ _______ _____ _____ _____ ________ __________ _______ _______ ___ _______.
___ __________ ___ ______ ____ ________.
___ _____ ______ ________ ______ ________ _____ _________ ______ _______ ____ ______.
______ ____ __________ ____ _____ __________ _____ _________ ______.
_________ _______ _________ ______ __________ _________ ___ ______ ______ _____ ______.
________ ___ _________ __________ _________ ________ __________ _________ ____ _________.
________ _____ _______ _____ ______ _________ _______.
_______ __________ _________ ___ ________ _______ _____ ________ ________.
________ _____ ____ _______ ______ ____ ___ ________ ___ _________ _________ _________.
______ _______ _____ ______ ________ _______ _____ ___.
____ _______ _______ ___ _______.
_________ _____ ______ ______ ___ __________ ___ ___.
______ ______ _________ ______ ______ _______.
_________ ___ ___ _____ ___.
_______ ____ __________ _______ __________ __________ ____ _______ _____ ____ ____.
_______ _________ _______ _____ _____ ___ ___ ______.
_________ __________ __________ ______ _______ _______ ________ _________ ____.
________ _____ ____ __________ ______ _______ _________ _____.
________ ______ _______ ________ _________.
___ __________ ___ ____ ____.
___ ____ ______ __________ ________.
__________ _____ _____ ________ _________.
___ ________ ______ _________ ___ __________ _____ ________ ________ ____.
___ _______ __________ ___ _______ ___ ______ __________.
________ ____ ____ __________ ________ __________ _____ _________ ___.
_________ _________ ____ ___ ____ ____.
____ __________ ________ ________ _________ _________.
_________ _________ ____ _____ ________ _____ ____ ________ _______.
______ ______ _________ __________ ______ _________ __________ _________ __________ _______ _______.
_____ ________ ______ ______ _______ _______ ___ __________ ______ _____ ____ ____.
____ ______ __________ ______ ___.
__________ ____ ___ _____ ______ ___ _________ ___ ____ __________ ___ ____.
_____ _________ __________ _________ __________ _____ _____ _______.
___ __________ __________ __________ ______ __________ _____ _______ _______ _________ __________.
_________ _________ _______ _____ _________ ___ _______ ___ __________ _______.
_____ ________ _____ _______ _______.
___ _____ ______ ____ ________ ______.
___ _____ _________ _____ _________ _______ ________ _________ _________.
__________ ________ ________ _____ _______ _____ ___ ______ ___ _______.
___ ______ __________ _____ _______.
____ ____ ____ ___ ____ _____ __________ _________ ________.
__________ ___ __________ _____ ________.
____ _____ _____ ____ _______.
___ _______ _______ ___ ____ ____ __________.
___ ______ __________ _____ ______ _____ _______ ____ ________ ________.
__________ ___ ____ _______ ________ ___ ___.
___ __________ ________ ____ ________ _________.
_________ _____ ________ ___ _____.
________ ________ __________ _______ ________ _______ _____ ________ ____ ______.
_____ _______ ________ _____ ___ _____ _______ __________ ___ ___ _________.
______ ______ ______ _______ _________ _____ __________ _______.
______ ______ ______ ____ _______ ________ _______ _______.
_________ ________ __________ _________ ____.
____ _____ ____ ____ _________.
______ ______ ________ __________ _________ _________ ________ _____ __________ ______ _________ ____.
__________ _________ _______ ____ _________ ______ ________ __________ ____ _______ _______ ________.
___ __________ ______ ________ ________.
___ __________ ___ ________ ________ _________ __________ _______ _________ _________ _________ ____.
____ __________ ________ ___ __________ __________ ____ _____ __________ ________ __________ _______.
____ ___ ________ _________ ____ ___ ____ ___ _______ ________.
___ __________ _______ ________ ____ __________ _____ _______ _________.
_______ ___ _________ ____ ______ _______ _________ __________ _________.
__________ ___ _______ _________ ____ ________.
______ _______ _______ ____ __________.
__________ ____ ______ _____ ________ ____ ________.
Skip in 10
### Prim's Algorithm – Minimum Spanning Tree Consider a graph (not shown in your prompt), but to apply Prim’s Algorithm, the procedure is: 1. Choose any vertex as the starting vertex. 2. Select the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST. 3. Repeat until all vertices are included in the MST. Sample Example (to illustrate): Let’s assume a weighted graph with vertices: A, B, C, D, E And weighted edges: * A–B: 2 * A–C: 3 * B–C: 1 * B–D: 4 * C–D: 5 * C–E: 6 * D–E: 7 Prim's Algorithm Steps: 1. Start from vertex A. 2. Minimum edge from A is A–B (weight 2) → Add B to MST. 3. From A and B, pick minimum edge: B–C (1) → Add C to MST. 4. From A, B, C → B–D (4) → Add D to MST. 5. From A, B, C, D → C–E (6) → Add E to MST. Minimum Spanning Tree (MST) Edges: A–B (2), B–C (1), B–D (4), C–E (6) Total Weight: 13 > (Apply this method to the actual graph you have.) --- ### Sorting Algorithms Given List: `12, 5, 2, 15, 25, 30, 45, 8, 17,
_________ _____ _____ __________ ______.________ _____ _________ ________ _________ ________ ___ ________ _____ ______ __________.
___ ________ ____ ______ ______ ____ ________ ____ ____ _______ _________.
_____ ________ _________ _________ ____ _____ ________ ___ ______ ______ _______.
____ ________ __________ ____ _________ ____ ________ ____.
________ __________ ___ __________ ____ ______ ______ ____ __________.
____ ___ _______ _____ ___.
_________ ______ _______ _____ _____ _____ ________ __________ _______ _______ ___ _______.
___ __________ ___ ______ ____ ________.
___ _____ ______ ________ ______ ________ _____ _________ ______ _______ ____ ______.
______ ____ __________ ____ _____ __________ _____ _________ ______.
_________ _______ _________ ______ __________ _________ ___ ______ ______ _____ ______.
________ ___ _________ __________ _________ ________ __________ _________ ____ _________.
________ _____ _______ _____ ______ _________ _______.
_______ __________ _________ ___ ________ _______ _____ ________ ________.
________ _____ ____ _______ ______ ____ ___ ________ ___ _________ _________ _________.
______ _______ _____ ______ ________ _______ _____ ___.
____ _______ _______ ___ _______.
_________ _____ ______ ______ ___ __________ ___ ___.
______ ______ _________ ______ ______ _______.
_________ ___ ___ _____ ___.
_______ ____ __________ _______ __________ __________ ____ _______ _____ ____ ____.
_______ _________ _______ _____ _____ ___ ___ ______.
_________ __________ __________ ______ _______ _______ ________ _________ ____.
________ _____ ____ __________ ______ _______ _________ _____.
________ ______ _______ ________ _________.
___ __________ ___ ____ ____.
___ ____ ______ __________ ________.
__________ _____ _____ ________ _________.
___ ________ ______ _________ ___ __________ _____ ________ ________ ____.
___ _______ __________ ___ _______ ___ ______ __________.
________ ____ ____ __________ ________ __________ _____ _________ ___.
_________ _________ ____ ___ ____ ____.
____ __________ ________ ________ _________ _________.
_________ _________ ____ _____ ________ _____ ____ ________ _______.
______ ______ _________ __________ ______ _________ __________ _________ __________ _______ _______.
_____ ________ ______ ______ _______ _______ ___ __________ ______ _____ ____ ____.
____ ______ __________ ______ ___.
__________ ____ ___ _____ ______ ___ _________ ___ ____ __________ ___ ____.
_____ _________ __________ _________ __________ _____ _____ _______.
___ __________ __________ __________ ______ __________ _____ _______ _______ _________ __________.
_________ _________ _______ _____ _________ ___ _______ ___ __________ _______.
_____ ________ _____ _______ _______.
___ _____ ______ ____ ________ ______.
___ _____ _________ _____ _________ _______ ________ _________ _________.
__________ ________ ________ _____ _______ _____ ___ ______ ___ _______.
___ ______ __________ _____ _______.
____ ____ ____ ___ ____ _____ __________ _________ ________.
__________ ___ __________ _____ ________.
____ _____ _____ ____ _______.
___ _______ _______ ___ ____ ____ __________.
___ ______ __________ _____ ______ _____ _______ ____ ________ ________.
__________ ___ ____ _______ ________ ___ ___.
___ __________ ________ ____ ________ _________.
_________ _____ ________ ___ _____.
________ ________ __________ _______ ________ _______ _____ ________ ____ ______.
_____ _______ ________ _____ ___ _____ _______ __________ ___ ___ _________.
______ ______ ______ _______ _________ _____ __________ _______.
______ ______ ______ ____ _______ ________ _______ _______.
_________ ________ __________ _________ ____.
____ _____ ____ ____ _________.
______ ______ ________ __________ _________ _________ ________ _____ __________ ______ _________ ____.
__________ _________ _______ ____ _________ ______ ________ __________ ____ _______ _______ ________.
___ __________ ______ ________ ________.
___ __________ ___ ________ ________ _________ __________ _______ _________ _________ _________ ____.
____ __________ ________ ___ __________ __________ ____ _____ __________ ________ __________ _______.
____ ___ ________ _________ ____ ___ ____ ___ _______ ________.
___ __________ _______ ________ ____ __________ _____ _______ _________.
_______ ___ _________ ____ ______ _______ _________ __________ _________.
__________ ___ _______ _________ ____ ________.
______ _______ _______ ____ __________.
__________ ____ ______ _____ ________ ____ ________.
IGNOU ACADEMY
Your IGNOU journey, made easier.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
Continue Reading — It's Free
Sign in with Google to unlock more of this answer.
✓ Free access
✓ Unlock up to 60% of the answer
✓ No payment required
✓ Unlock up to 60% of the answer
✓ No payment required
Quick Google sign-in. No separate registration form.