Algorithms on Strings (Complete Course)

About Course
World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer science. To make sense of all that information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.

---------- TIME STAMP -----------------

SUFFIX TREES
0:00:00 From Genome Sequencing to Pattern Matching
0:08:20 Brute Force Approach to Pattern Matching
0:10:39 Herding Patterns into Trie
0:15:59 Herding Text into Suffix Trie
0:22:16 Suffix Trees

BURROWS-WHEELER TRANSFORM AND SUFFIX ARRAYS
0:27:16 Burrow-Wheeler Transform
0:31:53 Inverting Burrows-Wheeler Transform
0:38:55 using BWT for Pattern Matching
0:45:25 Suffix Arrays
0:50:54 Approximate Pattern Matching

KNUTH-MORRIS-PRATT ALGORITHM
0:57:38 Exact Pattern Matching
1:06:59 Safe Shift
1:10:05 Prefix Function
1:17:43 Computing Prefix Function
1:27:09 Knuth-Morris-Pratt Algorithm

CONSTRUCTING SUFFIX ARRAYS AND SUFFIX TREES
1:33:02 Suffix Array
1:39:52 General Strategy
1:46:35 Initialization
1:55:55 Sort Doubled Cyclic Shifts
2:03:57 SortDouble Implementation
2:10:34 Updating Classes
2:18:40 Full Algorithm
2:22:24 Suffix Array and Suffix Tree
2:31:23 LCP Array
2:36:47 Computing the LCP Array
2:42:48 Construct Suffix Tree from Suffix Array and LCP Array

⭐ Important Notes ⭐
⌨️ This course is created in collaboration with University of California

#algorithms,
#datastructures,
#algorithmsonstring,
#algorithmstring,