From eec70d435d564fea77f2449ab5faeb431043d2cc Mon Sep 17 00:00:00 2001 From: Mitja Felicijan Date: Mon, 24 Sep 2018 00:02:40 +0200 Subject: content update --- .../basic-math-in-programming/default.pug | 47 +++++++++++++++++++++- 1 file changed, 46 insertions(+), 1 deletion(-) (limited to 'slides/presentations/basic-math-in-programming/default.pug') diff --git a/slides/presentations/basic-math-in-programming/default.pug b/slides/presentations/basic-math-in-programming/default.pug index af5ee90..92b1474 100644 --- a/slides/presentations/basic-math-in-programming/default.pug +++ b/slides/presentations/basic-math-in-programming/default.pug @@ -16,11 +16,56 @@ section ul li We search for code example instead of algorithms. - li We copy and paste and do testing on trial&error principle. + li We copy and paste and do testing on trial&error principle. li We don't take enough time to properly understand problem we a re trying to solve. li Brute force solutions we make are usually not optimized +section + h2 Levenshtein distance + p The Levenshtein distance is a string metric for measuring difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. + + hr + + div.center + img(src="levenshtein-distance.svg") + + hr + + pre + code.language-python + | def levenshtein(seq1, seq2): + | oneago = None + | thisrow = range(1, len(seq2) + 1) + [0] + | for x in xrange(len(seq1)): + | twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1] + | for y in xrange(len(seq2)): + | delcost = oneago[y] + 1 + | addcost = thisrow[y - 1] + 1 + | subcost = oneago[y - 1] + (seq1[x] != seq2[y]) + | thisrow[y] = min(delcost, addcost, subcost) + | return thisrow[len(seq2) - 1] + + + hr + + h4 Going further + ol + li https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance + li https://en.wikipedia.org/wiki/Levenshtein_distance + li https://rosettacode.org/wiki/Levenshtein_distance + + + + + + + + + + + + section h2 Basic linear algebra -- cgit v1.2.3