Mathematics for Data Science 1 - W11_L8: Minimum cost spanning trees | prim’s & kruskal’s algorithms

Welcome to Week 11 Lecture 8 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 the Minimum Cost Spanning Tree (MST) problem in weighted graphs, a cornerstone of graph theory with wide-ranging applications. We explore real-world scenarios such as designing cost-efficient road networks after natural disasters and building reliable internet infrastructure. The lecture revisits the fundamental properties of trees and then presents two powerful algorithmic approaches for finding MSTs: Prim’s Algorithm, which grows a tree from a single starting vertex by repeatedly adding the smallest edge, and Kruskal’s Algorithm, which builds the MST by successively joining disconnected components with the smallest available edge. Examples illustrate how these algorithms ensure connectivity with minimum cost. 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 #MinimumSpanningTree #MST #WeightedGraphs #GraphAlgorithms #PrimsAlgorithm #KruskalsAlgorithm #TreeDataStructure #DataStructures #Algorithms #ShortestPath #GraphTheory #Connectivity #ComputerScience