Algorithms on Strings
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. In this online course you will learn key pattern matching concepts: tries, suffix trees, suffix arrays and even the Burrows-Wheeler transform.
Buy Now AED 274.99 + VAT
Monthly Subscription Starting at AED 99 + VAT
- Level Professional
- Duration 19 hours
- Course by University of California San Diego
-
Offered by
About
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. In this online course you will learn key pattern matching concepts: tries, suffix trees, suffix arrays and even the Burrows-Wheeler transform.Modules
From Genome Sequencing to Pattern Matching
-
6
Videos
-
3
Readings
-
1
Assignment
1
Assignment
- Tries and Suffix Trees
6
Videos
- Welcome
- From Genome Sequencing to Pattern Matching
- Brute Force Approach to Pattern Matching
- Herding Patterns into Trie
- Herding Text into Suffix Trie
- Suffix Trees
3
Readings
- Trie Construction - Pseudocode
- FAQ
- Slides and External References
Programming Assignment
-
2
Readings
-
1
Programming
- Programming Assignment 1
2
Readings
- Available Programming Languages
- FAQ on Programming Assignments
Burrows-Wheeler Transform
-
3
Videos
-
1
Readings
3
Videos
- Burrows-Wheeler Transform
- Inverting Burrows-Wheeler Transform
- Using BWT for Pattern Matching
1
Readings
- Using BWT for Pattern Matching
Suffix Arrays
-
1
Videos
-
1
Readings
1
Videos
- Suffix Arrays
1
Readings
- Pattern Matching with Suffix Array
Approximate Pattern Matching and Mutations of the Genome
-
1
Videos
1
Videos
- Approximate Pattern Matching
Slides and External References
-
2
Readings
2
Readings
- FAQ
- Slides and External References
Programming Assignment
-
1
Programming
-
1
Assignment
- Programming Assignment 2
1
Assignment
- Burrows-Wheeler Transform and Suffix Arrays
Knuth-Morris-Pratt Algorithm
-
8
Videos
-
2
Readings
-
1
Assignment
1
Assignment
- Exact Pattern Matching
8
Videos
- Exact Pattern Matching
- Skipping Positions
- Safe Shift
- Prefix Function
- Computing Prefix Function
- Implementation
- Analysis
- Knuth-Morris-Pratt Algorithm
2
Readings
- Programming Assignment 3 lasts for two weeks
- Slides and External References
Suffix Array Construction
-
8
Videos
-
2
Readings
-
1
Assignment
1
Assignment
- Suffix Array Construction
8
Videos
- Suffix Array
- General Construction Strategy
- Initialization
- Sort Doubled Cyclic Shifts
- SortDouble Implementation
- Updating Classes
- UpdateClasses Implementation
- Building Suffix Array
2
Readings
- Counting Sort
- Slides and External References
From Suffix Array to Suffix Tree
-
8
Videos
-
1
Readings
-
1
Programming
- Programming Assignment 3
8
Videos
- Suffix Array and Suffix Tree
- LCP Array
- Computing the LCP Array
- ComputeLCPArray Implementation
- Analysis
- Constructing Suffix Tree
- Implementation
- Analysis
1
Readings
- Slides and External References
Auto Summary
Discover the fascinating world of textual information with the "Algorithms on Strings" course, designed for IT and Computer Science enthusiasts. This professional-level course delves into the critical algorithms used by search engines to process and retrieve information efficiently, as well as their applications in personalized medicine for detecting genetic mutations. Under the expert guidance of Coursera instructors, you will explore essential pattern matching techniques including tries, suffix trees, suffix arrays, and the Burrows-Wheeler transform. With a comprehensive duration of 1140 minutes, this course offers a robust learning experience. Subscribe to the Starter plan and equip yourself with the knowledge to excel in the domain of string algorithms. Ideal for professionals looking to enhance their skills in computational text analysis and bioinformatics.
Neil Rhodes
Michael Levin
Michael Levin
Pavel Pevzner
Alexander S. Kulikov