Mathematics for Data Science 1 - W11_L1: Longest paths in DAGs – task scheduling & dependencies

Welcome to Week 11 Lecture 1 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 explores the application of Directed Acyclic Graphs (DAGs) to represent tasks with dependencies. We examine two fundamental problems: how to find a feasible sequence of tasks using topological sort, and how to determine the optimal number of steps (such as semesters) needed to complete all tasks when parallel execution is possible. The lecture highlights how computing the longest path in a DAG provides the minimum time required to finish all tasks, and shows how this can be achieved efficiently alongside topological sorting. 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 #DirectedAcyclicGraph #DAG #TopologicalSort #LongestPath #TaskScheduling #DependencyGraph #Algorithm #GraphTheory #ComputerScience #Optimization #ParallelExecution #ShortestDuration #FeasibleSchedule