cs215 ยป

CS215

CS215 Lesson 4

Solutions

Code for Magic Trick

Code for Lecture 11, Order Statistics:

f = open("yob1995.txt", "r")
maxname = "none"
maxval = 0
max2name = "none"
max2val = 0
for line in f:
    (name,sex,count) = line.rsplit(",")
    count = int(count)
    if sex == "F":
        if count > maxval:
            max2name = maxname
            max2val = maxval
            maxval = count
            maxname = name
        elif count > max2val:
            max2name = name
            max2val = count
print maxname, max2name
print maxval, max2val

Code for Lecture 18, Top K Code:

#
# List of distinct two-digit values.
# Where will 84 be located in the sorted version?
#
import random

L = [31, 45, 91, 51, 66, 82, 28, 33, 11, 89, 27, 36]

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

print partition(L, 84)
# >>>[31, 45, 51, 66, 82, 28, 33, 11, 27, 36, 84, 91, 89]

def top_k(L, k):
    v = L[random.randrange(len(L))]
    (left, middle, right) = partition(L, v)
    # middle used below (in place of [v]) for clarity
    if len(left) == k:   return left
    if len(left)+1 == k: return left + middle
    if len(left) > k:    return top_k(left, k)
    return left + middle + top_k(right, k - len(left) - len(middle))

print top_k(L, 5)
# >>> [31, 28, 33, 11, 27]
# list order may vary due to random selection of v

Code for Lecture 27, Down Heapify

# import random
# L = [random.randrange(90)+10 for i in range(20)]
L = [50, 88, 27, 58, 30, 21, 58, 13, 84, 24, 29, 43, 61, 44 ,65, 74, 76, 30, 82, 43]

#Heap shortcuts
def left(i): return i*2+1
def right(i): return i*2+2
def parent(i): return (i-1)/2
def root(i): return i==0
def leaf(L, i): return right(i) >= len(L) and left(i) >= len(L)
def one_child(L, i): return right(i) == len(L)

# Call this routine if the heap rooted at i satisfies the heap property
# *except* perhaps i to its immediate children
def down_heapify(L, i):
    # If i is a leaf, heap property holds
    if leaf(L, i): return
    # If i has one child...
    if one_child(L, i):
        # check heap property
        if L[i] > L[left(i)]:
            # if it fail, swap, fixing i and its child (a leaf)
            (L[i], L[left(i)]) = (L[left(i)], L[i])
        return
    # if i has two children...
    # check heap property
    if min(L[left(i)], L[right(i)]) >= L[i]: return
    # If it fails, see which child is the smaller
    # and swap i's value into that child
    # Afterwards, recurse into that child, which might violate
    if L[left(i)] < L[right(i)]:
        # Swap into left child
        (L[i], L[left(i)]) = (L[left(i)], L[i])
        down_heapify(L, left(i))
        return
    (L[i], L[right(i)]) = (L[right(i)], L[i])
    down_heapify(L, right(i))
    return

Code for Lecture 46, Remove_Min_solution

build_heap

def build_heap(L): for i in range(len(L)-1, -1, -1): down_heapify(L, i) return L