Fundamentals of Stringology I: Recap on Exact Pattern Matching and Alignment Algorithms
summary
Presents two concrete algorithmic results and how they work: an exact‑matching method that computes prefix‑match lengths Z[i] in linear time via the Z-algorithm using Z-box cases (explicit two‑finger scans only when needed) and finds all occurrences by forming P + separator + T; and an alignment DP that maximizes identical aligned pairs in O(NM) time, with constant‑time cell updates, plus the practical options of memoization and reducing space to O(N) while retaining correctness.
AI-written summary · about
chapters (27)
- 0:00Introduction to algorithms
- 1:37Exact string matching
- 3:07Terminology and pre-processing
- 4:56Concept of the z-box
- 7:19Computing z values
- 8:34The z algorithm cases
- 10:34Linear time z algorithm
- 13:09Correctness and analysis
- 16:20Algorithm time complexity
- 19:18Applications of z values
- 20:43Circular shift problem
- 23:16Exact matching in biology
- 26:01Introduction to inexact matching
- 28:25Sequence alignment definition
- 30:51Optimal alignment challenge
- 33:03Recursive alignment formula
- 35:21Analyzing alignment cases
- 37:00Calculating alignment values
- 38:43Recursive formula cases
- 40:04Finalizing the recurrence
- 42:36Dynamic programming approach
- 44:29Implementing dynamic programming
- 47:21Time complexity analysis
- 49:50Traceback and memoization
- 52:12Efficiency of memoization
- 55:32Pathfinding analogy
- 57:19Space optimization techniques
related talks
24mString Comparison in Real Life
54mDesign Patterns vs Anti pattern in APL
29mApplying Randomized Methods for Zonotope Enumeration and...
26mMathematical Approaches to Clustering
43mTopological data analysis: How to quantify "holes" in your data and why?
18mData Extraction via Semantic Regular Expression Synthesis
26mA Fast Algorithm for Computing the Maximum Weight Base in a Linear Matroid
33mPortable, type-fancy multidimensional arrays