Class 13  Notes
Upcoming Schedule
Project 3 is due at the beginning of class on Friday, 26 February, but you may not submit Project 3 until completing the Orange Belt level. If you are making clear progress towards completing the Orange Belt (see below), you may turn in Project 3 on Monday, 29 February with no penalty (still eligible for automatic Green Belt promotion with an excellent Project 3).
Orange Belt Promotion
If you received a Gold Star (or better!) on Project 2, congratulations  you are now an Orange Belt!
If you received a Green Star on Project 2, the standard way to be promoted to the Orange Belt level is to do these four things:

Complete Udacity cs101 Lesson 6: How to Have Infinite Power to make sure you understand recursive definition.

Answer Lesson 6: Problem Set: Question 4 ("Deep Count").

Answer Lesson 6: Problem Set 6 Starred: Question 1 ("Family Trees")

Define a
list_reverse
function that takes as input a list and returns a new list with the elements of the input list in reverse order. For example,list_reverse([1, 2, 3, 4])
should return[4, 3, 2, 1]
. You should define two versions of yourlist_reverse
function: one that uses a recursive call (and may not contain anyfor
orwhile
loops), and one that uses a loop (and may not contain a recursive call).
There is nothing to submit for 13. For questions 2 and 3, you should definitely try to solve these yourself and not look at the answer until you have made a serious attempt to solve it yourself. But, you may look at the answer if you are stuck. After looking at the answer, you should still write your own solution.
For question 4, you must work alone and solve this problem without help from anyone or using any external resources (other than the course staff).
To complete the Orange Belt, send your solution to #4 by email.
Slides
Code
Hammering Hamming
def hamming_distance_rec(s1, s2): assert len(s1) == len(s2) if not s1: return 0 else: return (not s1[0] == s2[0]) + hamming_distance_rec(s1[1:], s2[1:]) def hamming_distance_loop(s1, s2): assert len(s1) == len(s2) count = 0 for i in range(len(s1)): count = count + (not s1[i] == s2[i]) return count def hamming_distance_lc(s1, s2): assert len(s1) == len(s2) return sum([not e1 == e2 for (e1, e2) in zip(s1, s2)])
Time Trials
This is a simple (but not super accurate) way to estimate running times.
import sys, time, random, string def random_bases(n): return ''.join(random.choice(['A','C','G','T']) for i in range(n)) def time_hamming(n): s1 = random_bases(n) s2 = random_bases(n) for impl in [hamming_distance_rec, hamming_distance_loop, hamming_distance_lc]: start_time = time.clock() for count in range(1000): impl(s1, s2) stop_time = time.clock() print("Time for " + impl.__name__ + ": " + str(stop_time / start_time))
Edit Distance
def edit_distance(a, b): """ Returns the Levenshtein distance between a and b. """ if not (a and b): return len(a) + len(b) else: if a[0] == b[0]: return edit_distance(a[1:], b[1:]) else: return min(1 + edit_distance(a, b[1:]), # insert 1 + edit_distance(a[1:], b), # delete 1 + edit_distance(a[1:], b[1:])) # mutate
Nested Lists
def list_copy(lst): """Returns a shallow copy of the input lst.""" if not lst: return [] else: return [lst[0]] + list_copy(lst[1:]) def is_list(obj): """Returns True iff obj is a list.""" return isinstance(obj, list)
We didn't get to list_deep_copy
in class and will continue with this
Wednesday, but try to figure this out on your own (and how to turn it
into list_flatten
):
def list_deep_copy(lst): """Returns a deep copy of the input list.""" if not lst: return [] elif is_list(lst[0]): return [list_deep_copy(lst[0])] + list_deep_copy(lst[1:]) else: return [lst[0]] + list_deep_copy(lst[1:])
Demonstrate the difference between list_copy
and list_deep_copy
with some Python code that shows how they behave differently.