Recall & Review
beginner
What is the Edit distance (Levenshtein)?
It is the minimum number of single-character edits (insertions, deletions, or substitutions) needed to change one word into another.
Click to reveal answer
beginner
Which operations are counted in the Levenshtein distance?
Insertions, deletions, and substitutions of characters.
Click to reveal answer
beginner
Why is Edit distance useful in NLP?
It helps measure how similar two words or strings are, useful for spell checking, autocorrect, and fuzzy matching.
Click to reveal answer
intermediate
How does the Levenshtein distance between "kitten" and "sitting" calculate?
The distance is 3: substitute 'k'→'s', substitute 'e'→'i', and insert 'g' at the end.
Click to reveal answer
intermediate
What is the time complexity of the standard dynamic programming algorithm for Levenshtein distance?
It is O(m×n), where m and n are the lengths of the two strings.
Click to reveal answer
Which of these is NOT an operation counted in Levenshtein distance?
✗ Incorrect
Levenshtein distance counts insertions, deletions, and substitutions, but not transpositions.
What does a Levenshtein distance of 0 between two strings mean?
✗ Incorrect
A distance of 0 means no edits are needed; the strings are exactly the same.
If you change 'cat' to 'cut', what is the Levenshtein distance?
✗ Incorrect
Only one substitution ('a' to 'u') is needed.
Which algorithmic approach is commonly used to compute Levenshtein distance?
✗ Incorrect
Dynamic programming efficiently computes the minimum edits by building a matrix of subproblems.
Levenshtein distance is useful in which NLP task?
✗ Incorrect
It helps find words close to a misspelled word for correction.
Explain what Edit distance (Levenshtein) measures and why it is important in NLP.
Think about how you fix typos or compare words.
You got /3 concepts.
Describe how the dynamic programming method calculates the Levenshtein distance between two strings.
Imagine filling a table step by step to find the answer.
You got /3 concepts.