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 recursive formulation of the Longest Common Subsequence (LCS) problem, discussing the naive implementation and the bottom-up approach for finding LCS. It also delves into recording optimal solutions, presenting pseudocode and analysis for LCS, and printing the solution. Furthermore, it introduces the concept of Optimal Binary Search Trees (BST), explaining how to build a BST with minimum expected search cost using probabilities. Examples are provided to illustrate the concepts, highlighting that the optimal BST may not have the smallest height or the highest-probability key at the root. The lecture concludes with discussions on the search cost of keys in an optimal BST and the optimal substructure for building a binary search tree.
This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.
Watch on Mediaspace