Get started with custom lists to organize and share courses.

Sign up

Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

  • Provider Coursera
  • Subject Algorithms and Data Structures
  • Cost Free Online Course (Audit)
  • Session In progress
  • Language English
  • Certificate Paid Certificate Available
  • Start Date
  • Duration 4 weeks long
  • Learn more about MOOCs

Taken this course? Share your experience with other students. Write review

Overview

Sign up to Coursera courses for free Learn how

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.

Syllabus

Suffix Trees
How would you search for a longest repeat in a string in LINEAR time? In 1973, Peter Weiner came up with a surprising solution that was based on suffix trees, the key data structure in pattern matching. Computer scientists were so impressed with his algorithm that they called it the Algorithm of the Year. In this lesson, we will explore some key ideas for pattern matching that will - through a series of trials and errors - bring us to suffix trees.

Burrows-Wheeler Transform and Suffix Arrays
Although EXACT pattern matching with suffix trees is fast, it is not clear how to use suffix trees for APPROXIMATE pattern matching. In 1994, Michael Burrows and David Wheeler invented an ingenious algorithm for text compression that is now known as Burrows-Wheeler Transform. They knew nothing about genomics, and they could not have imagined that 15 years later their algorithm will become the workhorse of biologists searching for genomic mutations. But what text compression has to do with pattern matching??? In this lesson you will learn that the fate of an algorithm is often hard to predict – its applications may appear in a field that has nothing to do with the original plan of its inventors.

Knuth–Morris–Pratt Algorithm
Congratulations, you have now learned the key pattern matching concepts: tries, suffix trees, suffix arrays and even the Burrows-Wheeler transform! However, some of the results Pavel mentioned remain mysterious: e.g., how can we perform exact pattern matching in O(|Text|) time rather than in O(|Text|*|Pattern|) time as in the naïve brute force algorithm? How can it be that matching a 1000-nucleotide pattern against the human genome is nearly as fast as matching a 3-nucleotide pattern??? Also, even though Pavel showed how to quickly construct the suffix array given the suffix tree, he has not revealed the magic behind the fast algorithms for the suffix tree construction!In this module, Miсhael will address some algorithmic challenges that Pavel tried to hide from you :) such as the Knuth-Morris-Pratt algorithm for exact pattern matching and more efficient algorithms for suffix tree and suffix array construction.

Constructing Suffix Arrays and Suffix Trees
In this module we continue studying algorithmic challenges of the string algorithms. You will learn an O(n log n) algorithm for suffix array construction and a linear time algorithm for construction of suffix tree from a suffix array. You will also implement these algorithms and the Knuth-Morris-Pratt algorithm in the last Programming Assignment in this course.

Taught by

Pavel Pevzner, Alexander S. Kulikov and Michael Levin

Help Center

Most commonly asked questions about Coursera Coursera

Reviews for Coursera's Algorithms on Strings
2.5 Based on 4 reviews

  • 5 star 0%
  • 4 star 25%
  • 3 star 25%
  • 2 star 25%
  • 1 star 25%

Did you take this course? Share your experience with other students.

Write a review
  • 1
Anonymous
1.0 3 years ago
Anonymous completed this course.
The concepts in the first two weeks are poorly taught. You have to either read some books or watch videos from somewhere else to understand the concepts.
0 person found
this review helpful
Was this review helpful to you? Yes
Alex I
3.0 3 years ago
Alex completed this course.
0 person found
this review helpful
Was this review helpful to you? Yes
Steven O
2.0 3 years ago
Steven completed this course.
0 person found
this review helpful
Was this review helpful to you? Yes
Ivan V
4.0 3 years ago
Ivan completed this course.
Was this review helpful to you? Yes
  • 1

Class Central

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free

Never stop learning Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.