Lab Week 3

Imported Code

Project Code

def _binarySearch(l, x): if l == []: raise Exception() m = len(l)/2 # halfway, or one past halfway if l[m] == x: return m # found it! if l[m] < x: return _binarySearch(l[m+1:], x) + m + 1 # do it again on the top half (minus the middle) return _binarySearch(l[:m], x) # do it again on the bottom half (minus the middle) def binarySearch(l, x): try: print _binarySearch(l, x) except: print "not found"

Commands

binarySearch(['alpha', 'beta', 'gamma', 'delta'], 'alpha') binarySearch(['alpha', 'beta', 'gamma', 'delta'], 'omega')

Output

Imported Code

Project Code

def _radixSort(l, d): for i in range(d): s = [[] for _ in range(10)] for j in l: s[((j // (10 ** i)) % 10)].append(j) l = [] for j in s: l.extend(j) return l def radixSort(l): d = 0 for i in l: d = max(d, len(str(i))) # work out what the longest number is print _radixSort(l, d)

Commands

radixSort([1,6,2,7,3,8,4,9,5,0])

Output

Imported Code

Project Code

def _countSort(l, a, b): s = [0 for _ in range(b - a + 1)] for i in l: s[i - a] += 1 for i in range(1, b - a + 1): s[i] += s[i-1] r = [0 for _ in range(s[b - a])] for i in range(s[b - a] - 1, -1, -1): s[l[i] - a] -= 1 r[s[l[i] - a]] = l[i] return r def countSort(l): a = 0 b = 0 for i in l: a = min(a, i) b = max(b, i) print _countSort(l, a, b)

Commands

countSort([1,6,2,7,3,8,4,9,5,0])

Output

Imported Code

Project Code

import random recursiveCount = 0 def _randQSort(l, i, j): if (i + 1) >= j: return 0 k = random.randint(i,j-1) # find the pivot element l[k], l[j-1] = l[j-1], l[k] # swap it with the far right of the array m = i # begin the swapping! for n in range(i, j): if l[n] <= l[j-1]: l[m], l[n] = l[n], l[m] m += 1 global recursiveCount recursiveCount += 1 _randQSort(l, i, m-1) _randQSort(l, m, j) def randQSort(l): global recursiveCount recursiveCount = 0 _randQSort(l, 0, len(l)) print l print recursiveCount

Commands

randQSort([1,6,2,7,3,8,4,9,5,0])

Output

Imported Code

Project Code

def choose(n, k): if (k == 0) | (k == n): return 1 if (k < 0) | (k > n): return 0 return choose(n-1, k) + choose(n-1, k-1)

Commands

print choose(20, 7)

Output

Imported Code

Project Code

def _chooseMemo(n, k, m): if (k == 0) | (k == n): return 1 if (k < 0) | (k > n): return 0 if m[n][k] is None: # we have yet to find this value, so let's memo it m[n][k] = _chooseMemo(n-1, k, m) + _chooseMemo(n-1, k-1, m) return m[n][k] def chooseMemo(n, k): m = [[None for x in range(n + 1)] for x in range(n + 1)] # create an n*n array, initialised to None return _chooseMemo(n, k, m)

Commands

print chooseMemo(20, 7)

Output