Day 8

Today

• Dictionaries and Tuples
• More Recursion Practice
• Studio time

For next time

• MP2 is due Tuesday. If you’d like to participate in the gallery show, please email your art files and artist’s statement to Ben by Monday evening at the latest

Reading Journal Debrief

With the person sitting next to you, review your solutions to the most_frequent exercise. Pay particular attention to your strategies for iteration and sorting.

“Recursive” problem analysis from 5 Whys, introduction and Examples and An Introduction to 5-why: What is the value in continuing to ask “why”? How do you know when you’ve reached a root cause?

Review: Python types

Now that we’ve read about Dictionaries and Tuples, we’ve seen almost all built-in Python types (and our next stop will be to begin designing our own custom objects). As an activity, let’s compare and contrast the built-in types and their uses. Some dimensions to consider:

• mutable/immutable
• iterable?
• what other types can it contain (if any)
• “truthy”/”falsy” values
• common uses

Recursion Practice

Let’s circle back on some of the recursion practice problems from last time. Make sure you have an implementation of choose(n, k) - we’ll use dictionaries to improve its performance next time.

Levenshtein Distance

Write a function called levenshtein_distance that takes as input two strings and returns the Levenshtein distance between the two strings. Intuitively, the Levenshtein distance is the minimum number of edit operations to transform one string into the other (for this reason Levenshtein distance is sometimes called “edit distance”). These edits can either be insertions, deletions, or substitutions. Note that Levenshtein distance is similar to Hamming distance, but works for strings of differing lengths

Here are some examples of these operations:

1. kitten → sitten (substitution of s for k)
2. sitten → sittin (substitution of i for e)
3. sittin → sitting (insertion of g at the end).

While this function seems initially daunting, it admits a very compact recursive solution. You can either work on your own to see the recursive solution, or use the recursive solution given in the Wikipedia article.

To get a better handle on this, let’s consider some more examples.

levenshtein_distance('kitten', 'smitten') -> 2 (see below for steps)

1. kitten → sitten (k gets replaced by s)
2. sitten → smitten (insert between s and i)

levenshtein_distance('beta', 'pedal') -> 3 (see below for steps)

1. beta → peta (b gets replaced by p)
2. peta → petal (l gets inserted at the end)
3. petal → pedal (t gets replaced by d)

levenshtein_distance('battle', 'bet') -> 4 (see below for steps)

1. battle → bettle (a gets replaced by e)
2. bettle → bettl (the last e gets deleted)
3. bettl → bett (delete l)
4. bett → bet (delete t)

Base Cases

Let’s consider the base cases when one of the two strings is empty. What should the Levenshtein distance be in this case?

Recursive Step

Let’s consider the different ways in which we can make the first character of string a equal to the first character of string b. Here are the possible cases.

• The first two characters are already equal
• Replace the first character of string a with the first character of string b
• Insert the first character of string b before the characters of string a
• Delete the first character of string a

For each of these steps we have to consider two things:

• How much does this first step cost?
• How much does it cost to make the rest of the two strings equal to each other

Let’s write a recursive implementation of this function.

Turtle World

You can also revisit Turtle World one last time and pursue one of the fractal drawing activities from last class. One additional bit of fun: now that we know about tuples, we’re not limited to a tiny color palette. Colors in computer graphics are typically expressed as a (red, green, blue) tuple, which you can pass to turtle.color to paint the entire rainbow!