Mathematics for Data Science 1 - W11_L10: Minimum cost spanning trees | kruskal’s algorithm

Welcome to Week 11 Lecture 10 of the course "Mathematics for Data Science I" by Profs. Neelesh Upadhye, Madhavan Mukund. Full Course: https://study.iitm.ac.in/ds/course_pages/BSMA1001.html Video Overview This lecture introduces Kruskal’s Algorithm, an alternative greedy approach for constructing the Minimum Cost Spanning Tree (MCST) in weighted, undirected, and connected graphs. Unlike Prim’s Algorithm, which grows a single tree, Kruskal’s Algorithm starts with all vertices as separate components and repeatedly adds the smallest available edge that connects two different components, while avoiding cycles. We walk through worked examples to illustrate the process and discuss how repeated edge weights can lead to different valid spanning trees. The lecture also compares Kruskal’s and Prim’s Algorithms, emphasizing their similarities, differences, and the shared theoretical foundation via the minimum separator lemma. About IIT Madras' online Bachelor of Science programme IIT Madras offers four-year BS programmes that aim to provide quality education to all, irrespective of age, educational background, or location. The BS programme has multiple levels, which provide flexibility to students to exit at any of these levels. Depending on the courses completed and credits earned, the learner can receive a Foundation Certificate from IITM CODE (Centre for Outreach and Digital Education), Diploma(s) from IIT Madras, or BSc/BS Degrees from IIT Madras. For more details, visit: https://www.iitm.ac.in/academics/study-at-iitm/non-campus-bs-programmes #KruskalAlgorithm #MinimumCostSpanningTree #MCST #GraphTheory #Algorithms #DataStructures #WeightedGraphs #SpanningTree #PrimAlgorithm #MST #MinimumSeparatorLemma #GreedyAlgorithm #ConnectedGraphs