Explore
For Enterprise
Join for Free
Log In

Arts et humanités
Business
Informatique
Science des données
Technologies de l'information
Santé
Mathématiques et logique
Développement personnel
Sciences physiques et ingénierie
Sciences sociales
Apprentissage des langues
University of London
BSc in Computer Science applications open next week
University of London's Bachelor of Computer Science application opens December 16th.
University of Michigan
Earn a master's in data science from Michigan
Launch your data science career with a degree from one of the world’s best schools of information
Diplômes
Certificats

Explorez l'intégralité de Coursera

Parcourir
Top Courses
For Enterprise
Connexion
Inscrivez-vous gratuitement

Computing Edit Distance

Loading...

Algorithmic Toolbox

Université de Californie à San Diego

4.7 (5,490 évaluations) | 170K étudiants inscrits

Cours 1 de 6 dans Structures de données et algorithmes Spécialisation

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second). Do you have technical problems? Write to us: coursera@hse.ru

Visualiser le programme de cours

Compétences que vous apprendrez

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Avis

4.7 (5,490 évaluations)

5 stars
4,079 ratings
4 stars
1,121 ratings
3 stars
197 ratings
2 stars
40 ratings
1 star
53 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

AG

Aug 06, 2019

Thanks for the course, it was instructive! I like that some problems require implementing algorithms discussed in lectures, while others are quite challenging and are very satisfying to solve :)

À partir de la leçon

Dynamic Programming 1

In this final module of the course you will learn about the powerful algorithmic technique for solving many optimization problems called Dynamic Programming. It turned out that dynamic programming can solve many problems that evade all attempts to solve them using greedy or divide-and-conquer strategy. There are countless applications of dynamic programming in practice: from maximizing the advertisement revenue of a TV station, to search for similar Internet pages, to gene finding (the problem where biologists need to find the minimum number of mutations to transform one gene into another). You will learn how the same idea helps to automatically make spelling corrections and to show the differences between two versions of the same text.

The Alignment Game8:39

Computing Edit Distance6:37

Reconstructing an Optimal Alignment4:55

Enseigné par

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Transcription

Let's now see how dynamic programming algorithm solves the edit distance problem. We start by considering two strings, A of length n and B of length m and we will ask the question question what is an optimal alignment of an i-prefix of A, which is the first i symbols of A, and the j-prefix of B which are the first j symbols only. The last column of an optimal alignment is either an insertion or a deletion or a mismatch, or a match. And please notice that if we remove the last column from the optimal alignment of the strings, what is left is an optimal alignment of the corresponding two prefixes. And we can adjust the score of the optimal alignment for i prefix and j prefix by adding plus 1 in the case of insertion, plus 1 in the case of deletion, plus 1 in the case of mismatch and adding nothing in the case of match. Let's denote D (i, j) to be the edit distance between an i-prefix and a j-prefix. And in this case, this figure at the top of the slide illustrates the following recurrency. D(i,j) equal to the minimum of the following four values: D(i,j-1)+1, D(i-1,j)+1, D(i-1,j-1)+1, in the case the last two symbols in the i prefix of A and j prefix of B are different. And D(i- 1, j- 1), if the last symbols in i and j prefix are the same. Our goal now is to compute the edit distance D, i, j between all i prefixes of string A and all j prefixes of string B. In the case of string editing and distance we will construct eight by nine grid and our goal is to compute all edit distances D(i, j) corresponding to all nodes in this grid. For example, for i and j equal to four and four. How will we compute the corresponding distance D(i, j)? Let's start by filling distances D(i, 0) in the first column of this matrix. It is easy because indeed we are comparing an i-prefix of string A against a 0-prefix of string D and therefore this edit distance for i-prefix will be equal to i. That's what's shown here, similarly we can easily fill the first row in this matrix. And now let's try to compute what will be the distance D(1,1) corresponding to comparison of string consisting of single symbol E, with a string consisting of single symbol D, there are three possible ways to arrive to the node (1, 1): from the nodes (0, 0), (0, 1), and (1, 0). Which one should be the way we will select to find the optimal edit distance. According to the previous recurrency, we should select the one of three directions that gives minimal value for D(i, j), which is minimum of 2, 2, and 1 and therefore we arrive to node (1, 1) by diagonal edge. Let's keep this in memory that the right direction to arrive at node (1, 1) was the diagonal direction. We will now try to compute the edit distance for the next node in the matrix. And in this case D(2,1) is equal to minimum D(2,0) + 1, D(1,1) + 1 and D(1,0) of each tells us that's the optimal way to arrive to this node would be again, by diagonal edge. You continue further, once again compare three values and it turn out that the best way to arrive to this node will be by vertical edge. We'll continue further and we'll fill the whole second column in the matrix. Now let's continue with the circle, what about this node? For this node D(1,2) = minimum {D(1,1) + 1, D (0,2) + 1, and D (0,1) + 1}. And it is minimum of 2, 3, and 2. In fact, there are two optimal ways to arrive to this node and in this case we show both of them by diagonal edge into this vertex and by horizontal edge of this vertex. You'll continue further and slowly but surely we will fill the whole matrix. The edit distance pseudocode implements the algorithm we just discussed. It first fills in the first column and the first row of the dynamic programming matrix and then it continues filling it up by computing the cost of moving to vertex (i, j) using insertion, deletion, or mismatch or match or in other words, exploring all possibility. Moving to the vertex i, j using vertical edge, horizontal edge, and diagonal edge. And then it finds out which of these possibilities results in the minimum edit distance.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera

À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté

Étudiants
Partenaires
Développeurs
Testeurs bêta
Traducteurs
Blog
Blog Tech

Plus

Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales

Apprendre partout

Suivez-nous

© 2019 Coursera Inc. Tous droits réservés.