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
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