Dynamic Programming: Palindromic Subsequences

This lecture covers dynamic programming algorithms for finding palindromic subsequences in a given sequence of characters. It starts by defining palindromes and then presents a dynamic programming solution to find the longest palindromic subsequence in a sequence. The lecture also discusses the design and analysis of the algorithm, emphasizing its time complexity and recursive formulas. Additionally, it explores a bottom-up implementation of the recursion and analyzes its running time. Furthermore, the lecture delves into merging binary search trees, providing an algorithm to merge multiple binary search trees into a balanced binary search tree efficiently. The lecture concludes with a problem related to finding the median of two sorted arrays and its algorithmic design and analysis.