CSC 15: Recursion Challenge #### Only the first problem: "Mergesort" is required 1. Mergesort. First, implement the "bubblesort" algorithm for comparison: def bubblesort(A): n = len(A) i = 0 # outer loop counter while iA[j+1]: A[j],A[j+1] = A[j+1],A[j] # swap j +=1 # while j i += 1 # while i # bubbelsort # Bubblesort is "destructive". A more sophisticated sorting algorithm is "mergesort" which works as follows. Given a list such as [6,4,2,8,1,7,3,5], split the list into two halfs: [6,4,2,8] and [1,7,3,5]. Now RECURSIVELY mergesort the two halfs. This gives you two small sorted lists: [2,4,6,8] and [1,3,5,7]. Now you must "merge" the two lists by forming a new list as follows. Keep track of two couters for the two lists: i and j (both starting at 0). At each step, append to the new list the lesser of the two elements B[i] and C[j], where B and C represent the two halfs. Then increment either i or j, depending on which value was chosen. For example, merging [1,3,4,7,8] and [5,6,10] will give you the list [1,3,4,5,7,8,10]. In this example, i was incremented 3 times before j was implemented. (Warning: the merge loop can be a bit tricky to write since the two arrays are of different lengths: you can reach the end of one before the other, so you need to be very careful about avoiding array out-of-bounds errors). You can divide a list into two halfs as follows: B = A[0:len(A)/2] C = A[len(A)/2:len(A)] In general, A[start:end] gives you the sublist of A from A[start] to A[end-1]. Finally, your procedure needs to know when to stop the recursion. That is, your procedure needs to recognize the simple cases of when the list to be sorted contains zero or one element. That is, a list such as [] or [3] is already sorted, so the recursion stops. The mergesort algorithm works by recursively breaking down the problem until the "base" non-recursive case is reached. Implement this algorithm as a function mergesort(A). Any other procedure you need must be encapsulated inside. Note that mergesort will be "non-destructive" since you'll be building new lists. ## timing experiments Note that, unlike bubblesort, the mergesort algorithm as described is non-destructive: it creates a new array each time. It will use a lot more memory than bubblesort. But will it be slower or faster? Speculate as to why (write down your reasoning in comments), then run timing experiments (see sorts.py on homepage on how to do timing experiments in Linux). Compare running times of bubblesort and mergesort on different sizes of large, randomly generated arrays. #### MEGA Challenge: 2. A list in Python can contain nested lists. For example, with A = [2,[3,4],[[[5]]], [[2,7],[5,[6]]]] A[0] is 2, A[1] is [3,4], A[2] is [[[5]]]. A[1][0] is the first element of A[1], namely 3. You can determine if something is a list using the 'isinstance' predicate. For example, isinstance([1,2],list) returns True and isinstance(4,list) returns False. Write a function to "flatten" a possibly-nested list such as A above into a one-level list. For example, flatten(A) should return the list [2,3,4,5,2,7,5,6] and flatten([2,[4,5,6,[7]]]) will return [2,4,5,6,7], etc .. Hint: think recursively. the program shouldn't be long. Remember also: A.append(x) adds new element x destructively to A. A = A+B : appends two *lists* A and B: [1,2] + [3,4] == [1,2,3,4]. Careful: if A and B are both lists, then A.append(B) will create a list within a list: [1,2].append([3,4]) creates [1,2,[3,4]]. append and + work very differently. #### GIGA Challenge: 3. Write a program to compute all the permutations of a string. For example, permute("abc") should return ["abc", "acb", "bac", "bca", "cab", "cba"] The order doesn't matter and repeats doesn't matter. hint: if you can't permute a string with n characters, try to permute one with n-1 characters. Even a lowly earthling can permute a string with only one character. The non-destructive operation S.remove("a","") removes the character "a" from string s (replaces it with empty string). For example: s = "abc" t = s.remove("b","") # t is now equal to "ac", s is still "abc" #### 3b. Computing the permutation takes a long time. There are n! permutations of a string with n characters, and n! gets very big bery fast. One way to improve matters is to store the previous results of permutation computations in a hash table. That is, after you've computed permutation("abc"), don't just throw the result away. Store it in a global hash table. Now the next time the same permutation is needed, we only have to look up the hash table. Write a version of the permutation function that does this automatically. Can you generalize your solution by adopting to the fibonacci function? That is, the version of the fibonacci function that makes two recursive calls is very inefficient. With this technique the inefficiency can be eliminated. This is called "memoizing", also "dynamic programming".