Dynamic Programming: Solving Longest Common Subsequence and Voice Recognition Problems
Explore dynamic programming through examples like finding the longest common subsequence and solving voice recognition problems using Viterbi's algorithm. Understand the design process, subproblems, decisions, and optimal solutions involved in dynamic programming algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Example 3: Longest Common Subsequence Input: two strings a[] = ababcde and b[] = abbecd Subsequence: same definition as in LIS (can skip characters) E.g. abac is a subsequence of a[], but not b[] abed is a subsequence of b[] but not a[] Goal: Find the length of the longest common subsequence (LCS) In this example: LCS = abbcd , length = 5.
Designing a DP algorithm for LCS Step 1: think of the problem as making a seq. of decisions For any pair of characters, decide whether they are matched in the Longest Common Subsequence Step 2: Focus on last decision, enumerate the options For the last characters of both sequence, they are either both in LCS, or not Step 3: Try to relate each option to a smaller subproblem Subproblem: Longest Common Subsequence of two Prefixes. both in LCS: both sequences are now shorter not (one of them is not in LCS): one of the sequences is now shorter
Example 4 Viterbis Algorithm Consider a simplified version of a voice recognition problem Goal: Given n segments of sounds, output the phonemes (e.g. / fo ni m/) each sound might represent one of k phonemes. Input: For each sound segment, a list of scores for the k phonemes. For every pair of phonemes, a score for how likely one comes after the other Goal: Find a sequence of phonemes that has the highest score.
Example n = 3, k = 2 Input: Phoneme\Sound 1 2 3 1 5 5 4 2 1 3 2 Phoneme\Phoneme 1 2 1 1 5 2 4 2 Optimal solution: 1 2 1 Score = (5 + 3 + 4) + (5 + 4) = 21
Designing a DP algorithm for Voice Recognition Step 1: think of the problem as making a seq. of decisions For each sound segment, choose its phoneme Step 2: Focus on last decision, enumerate the options Choose the phoneme for last sound segment Problem: cost also depend on previous phoneme Solution: Fix the last phoneme and choose the second-to-last Step 3: Try to relate each option to a smaller subproblem Subproblem: optimal choice for sound segments 1..m, the k-th segment chooses phoneme p.
