• Duración:
    4 semanas
  • Dedicación:
    8–10 horas por semana
  • Precio:

    GRATIS
    Agregar un Certificado Verificado por $150 USD

  • Institución
  • Tema:
  • Nivel:
    Intermediate
  • Idioma:
    English
  • Transcripción de video:
    English
  • Tipo de curso:
    A tu ritmo

Programas asociados:

Prerrequisitos

Basic knowledge of at least one programming language. Successful completion of the Algorithmic Designs and Techniques and Data Structures Fundamentals courses.

Sobre este curso

Omitir Sobre este curso

The world and internet are full of textual information. We search for information using textual queries and read websites, books and e-mails.

These are all strings from a computer science point of view. To make sense of all this 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 course, part of the Algorithms and Data Structures MicroMasters program, you will learn about:

  • suffix trees;
  • suffix arrays;
  • how other brilliant algorithmic ideas help doctors to find differences between genomes;
  • power lightning-fast Internet searches.

Lo que aprenderás

Omitir Lo que aprenderás
  • Key ideas for pattern matching and suffix trees
  • Suffix arrays
  • Burrows-Wheeler Transform for compression
  • Applications of string algorithms in bioinformatics

Plan de estudios

Omitir Plan de estudios

Weeks 1 and 2: 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.

Week 3 and 4: 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.

Conoce a tus instructores

Pavel Pevzner
Ronald R. Taylor Professor of Computer Science
The University of California, San Diego
Michael Levin
Chief Data Scientist
Yandex.Market

Obtén un Certificado Verificado para destacar los conocimientos y las habilidades que adquieras
$150 USD

Ver un modelo de certificado de edX en PDF
  • Oficial y verificado

    Obtén un certificado con la firma del instructor y el logotipo de la institución para demostrar tus logros y aumentar las posibilidades de conseguir trabajo

  • Fácil de compartir

    Agrega el certificado a tu currículum o publícalo directamente en LinkedIn

  • Incentivo comprobado

    El certificado te da un motivo más para completar el curso

  • Apoya nuestra labor

    edX, una organización sin fines de lucro, se sustenta con los certificados verificados para financiar la educación gratuita para todo el mundo

Testimonios de los estudiantes

“This class makes string algorithms a very interesting and enjoyable topic. I would highly suggest taking this course. All the material is very well explained so you can really understand why it works and not only how! The programming assignments give you a hands-on experience implementing the different algorithm.”
-- Previous Student

¿Quién puede hacer este curso?

Lamentablemente, las personas de uno o más de los siguientes países o regiones no podrán registrarse para este curso: Irán, Cuba y la región de Crimea en Ucrania. Si bien edX consiguió licencias de la Oficina de Control de Activos Extranjeros de los EE. UU. (U.S. Office of Foreign Assets Control, OFAC) para ofrecer nuestros cursos a personas en estos países y regiones, las licencias que hemos recibido no son lo suficientemente amplias como para permitirnos dictar este curso en todas las ubicaciones. edX lamenta profundamente que las sanciones estadounidenses impidan que ofrezcamos todos nuestros cursos a cualquier persona, sin importar dónde viva.