Constant Factor Approximations to Edit Distance in Nearly Linear Time
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
Explore constant factor approximations to edit distance in nearly linear time through this 24-minute conference talk merging two papers. Delve into the main results and approximation techniques for edit distance. Learn about partitioning strings into windows, reducing to non-crossing matching, and handling dense graphs using triangle inequality. Discover methods for sparse graphs via "seed-and-expand" and union of disjoint bl-cliques. Examine searching for matches in both sparse and dense cases using the CDGKS algorithm. Investigate multiple levels in the sparse case and recap the key concepts presented by researchers from Stanford University, Charles University, and Rutgers University.
Syllabus
Intro
Approx ED
Main Result
Approximating ED
Partition strings into windows
Step 0: Reduction to non-crossing matching
Note: this step crucially uses triangle inequality!
Step 1: Dense graphs via triangle inequality
Sparse graphs via "seed-and-expand"
Union of disjoint bl-cliques
Searching for matches [KS]
Sparse case CDGKS
Dense case CDGKS
Multiple levels - sparse case [KS]
Recap
Taught by
Association for Computing Machinery (ACM)
Related Courses
Information TheoryThe Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera