# Day 8

## Today

• Tell us Tuesdays
• Intro to Toolboxes
• Dictionaries and Tuples
• More Recursion Practice
• Studio time

## Feedback for the class

Thank you for filling out the survey after MP1.

1. Your honest answers help us keep your workload in the sweet spot, where we are neither overwhelming nor boring you. We aim to have MP1 hit the sweet spot for challenge and time spent, but a large number of people ended up far from that spot - and we know that the connection to Bio in the first project is something that we can revisit.
• If you found MP1 to be difficult or time consuming, that is not at all unusual. We know that we’re diving right in to challenging problems while still learning and practicing programming skills. If you’re concerned or spending significantly more than the allotted hours on SoftDes, consider talking with us about how you can take more advantage of the course resources to support your learning.
• If you found the assignment quick or easy due to your past experience, please make sure you are continuing to challenge yourself via the Going Beyond options or talk to us about additional challenges.
2. The amount of Python scaffolding for MP1 seems appropriate, but we could use some more time spent on the biological concepts explored.

3. We collect information about the structure of the MP and RJs and consider them for how we scaffold future versions of the same assignment in the future, and when appropriate we use our learnings as we release subsequent RJs and MPs.

4. We learn how people are utilizing the help structures, such as Course Assistants.

5. This is a class where students can move at their own desired speed and make choices about what to pursue. We saw some people who had previous familiarity with the programming concepts in MP1 challenging themselves.

6. We’ve asked you to start considering your working styles and preferences (even though MP2 is a solo project) in preparation for team work in future projects - MP4 and beyond. There’s not a “right answer” to these questions, and we appreciate honest feedback however it comes in.

We are going to introduce “Tell us Tuesdays” to create an additional path for you to help us keep SoftDes in the sweet spot.

## Project Toolboxes Released Soon

Now that we’ve seen most of what Python has to offer, you’re well equipped to go off and explore on your own! The goal of the Project Toolbox exercises is to gain practice with a variety of interesting topics we won’t talk about in class. By completing them, you will develop a suite of skills that will allow you to do great things on the final project and beyond.

The first project toolbox is due Feb 28. If you’re looking for a easy place to get started, we suggest you check out Word Frequency Analysis, which goes well with the next Reading Journal and may help with the next Mini-project.

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. kittensitten (substitution of s for k)
2. sittensittin (substitution of i for e)
3. sittinsitting (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!