Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Lecture
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
This lecture covers the Master method for solving recurrences, introducing the Master Theorem to analyze algorithms. It then delves into the Maximum Subarray Problem, explaining the optimal solution structure and the concept of finding the maximum subarray that crosses the midpoint. The lecture explores brute force approaches, the importance of considering all possibilities, and the solution to finding the maximum subarray. It concludes with a detailed explanation of the FIND-MAX-CROSSING-SUBARRAY algorithm. Real-world scenarios, such as stock trading, are used to illustrate the practical applications of the discussed concepts.