Coding the Matrix: Linear Algebra through
Computer Science Applications
这次作业难度不小，第一个作业hw1还好，第二个全部都可以使用comprehension完成，但要小心返回值，还有深入理解本课程中的vector的概念。第三个作业难度不大，但一不小心就做错了，一个原因是grader不够智能，另一个原因就是细节问题了，比如某个函数的参数必须是set而不能是list。
这次作业总共花了大约7个小时，Making me gong Nut! 不过还学到了提交作业时的一个技巧，就是：
C:\Python33\python C:\Python33\submit_politics_lab.py --verbose
使用这个命令可以看到提交作业时何处出错，方便检查。
下面是三个子作业的代码：
#hw1
# Please fill out this stencil and submit using the provided submission script.
from GF2 import one
## Problem 1
p1_u = [ 0, 4]
p1_v = [-1, 3]
p1_v_plus_u = [-1,7]
p1_v_minus_u = [-1,-1]
p1_three_v_minus_two_u = [-3,1]
## Problem 2
p2_u = [-1, 1, 1]
p2_v = [ 2, -1, 5]
p2_v_plus_u = [1,0,6]
p2_v_minus_u = [3,-2,4]
p2_two_v_minus_u = [5,-3,9]
p2_v_plus_two_u = [0,1,7]
## Problem 3
# Write your answer using GF2's one instead of the number 1
p3_vector_sum_1 = [one,0,0]
p3_vector_sum_2 = [0,one,one]
## Problem 4
# Please express your solution as a set of the letters corresponding to the solutions.
# For example, {'a','b','c'} is the subset consisting of:
# a (1100000), b (0110000), and c (0011000).
# Leave an empty set if it cannot be expressed in terms of the other vectors.
u_0010010 = {'c','d','e'}
u_0100010 = {'b','c','d','e'}
## Problem 5
# Use the same format as the previous problem
v_0010010 = {'c','d'}
v_0100010 = set()
## Problem 6
uv_a = sum([5,0])
uv_b = sum([x*y for x,y in zip([0,1],[12345,6])])
uv_c = sum([x*y for x,y in zip([-1,3],[5,7])])
uv_d =sum([-1/2,-1/2])
## Problem 7
# use 'one' instead of '1'
x_gf2 = [one,0,0,0]
## Problem 8
v1 = [2,3,-4,1]
v2 = [1,-5,2,0]
v3 = [4,1,-1,-1]
第二个：
在这个作业中comprehension很重要
#vec.py
def getitem(v,d):
"Returns the value of entry d in v"
assert d in v.D
return v.f[d] if d in v.f else 0
def setitem(v,d,val):
"Set the element of v with label d to be val"
assert d in v.D
v.f[d]=val
def equal(u,v):
"Returns true iff u is equal to v"
assert u.D == v.D
return {getitem(u,x)==getitem(v,x) for x in v.D}=={True}
def add(u,v):
"Returns the sum of the two vectors"
assert u.D == v.D
return Vec(u.D,{x:getitem(u,x)+getitem(v,x) for x in v.D})
def dot(u,v):
"Returns the dot product of the two vectors"
assert u.D == v.D
return sum([getitem(u,x)*getitem(v,x) for x in v.D])
def scalar_mul(v, alpha):
"Returns the scalar-vector product alpha times v"
return Vec(v.D,{x:alpha*v.f[x] for x in v.f.keys()})
def neg(v):
"Returns the negation of a vector"
return Vec(v.D,{x:-y for x,y in v.f.items()})
##### NO NEED TO MODIFY BELOW HERE #####
class Vec:
"""
A vector has two fields:
D - the domain (a set)
f - a dictionary mapping (some) domain elements to field elements
elements of D not appearing in f are implicitly mapped to zero
"""
def __init__(self, labels, function):
self.D = labels
self.f = function
__getitem__ = getitem
__setitem__ = setitem
__neg__ = neg
__rmul__ = scalar_mul #if left arg of * is primitive, assume it's a scalar
def __mul__(self,other):
#If other is a vector, returns the dot product of self and other
if isinstance(other, Vec):
return dot(self,other)
else:
return NotImplemented # Will cause other.__rmul__(self) to be invoked
def __truediv__(self,other): # Scalar division
return (1/other)*self
__add__ = add
def __radd__(self, other):
"Hack to allow sum(...) to work with vectors"
if other == 0:
return self
def __sub__(a,b):
"Returns a vector which is the difference of a and b."
return a+(-b)
__eq__ = equal
def __str__(v):
"pretty-printing"
try:
D_list = sorted(v.D)
except TypeError:
D_list = sorted(v.D, key=hash)
numdec = 3
wd = dict([(k,(1+max(len(str(k)), len('{0:.{1}G}'.format(v[k], numdec))))) if isinstance(v[k], int) or isinstance(v[k], float) else (k,(1+max(len(str(k)), len(str(v[k]))))) for k in D_list])
# w = 1+max([len(str(k)) for k in D_list]+[len('{0:.{1}G}'.format(value,numdec)) for value in v.f.values()])
s1 = ''.join(['{0:>{1}}'.format(k,wd[k]) for k in D_list])
s2 = ''.join(['{0:>{1}.{2}G}'.format(v[k],wd[k],numdec) if isinstance(v[k], int) or isinstance(v[k], float) else '{0:>{1}}'.format(v[k], wd[k]) for k in D_list])
return "\n" + s1 + "\n" + '-'*sum(wd.values()) +"\n" + s2
def __repr__(self):
return "Vec(" + str(self.D) + "," + str(self.f) + ")"
def copy(self):
"Don't make a new copy of the domain D"
return Vec(self.D, self.f.copy())
第三个：
使用带lambda的max可以用到
voting_data = list(open("voting_record_dump109.txt"))
## Task 1
def create_voting_dict():
"""
Input: None (use voting_data above)
Output: A dictionary that maps the last name of a senator
to a list of numbers representing the senator's voting
record.
Example:
>>> create_voting_dict()['Clinton']
[-1, 1, 1, 1, 0, 0, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1]
This procedure should return a dictionary that maps the last name
of a senator to a list of numbers representing that senator's
voting record, using the list of strings from the dump file (strlist). You
will need to use the built-in procedure int() to convert a string
representation of an integer (e.g. '1') to the actual integer
(e.g. 1).
You can use the split() procedure to split each line of the
strlist into a list; the first element of the list will be the senator's
name, the second will be his/her party affiliation (R or D), the
third will be his/her home state, and the remaining elements of
the list will be that senator's voting record on a collection of bills.
A "1" represents a 'yea' vote, a "-1" a 'nay', and a "0" an abstention.
The lists for each senator should preserve the order listed in voting data.
"""
return {x.split()[0]:[int(y) for y in x.split()[3:]] for x in voting_data}
## Task 2
def policy_compare(sen_a, sen_b, voting_dict):
"""
Input: last names of sen_a and sen_b, and a voting dictionary mapping senator
names to lists representing their voting records.
Output: the dot-product (as a number) representing the degree of similarity
between two senators' voting policies
Example:
>>> voting_dict = {'Fox-Epstein':[-1,-1,-1,1],'Ravella':[1,1,1,1]}
>>> policy_compare('Fox-Epstein','Ravella', voting_dict)
-2
"""
return sum([x*y for (x,y) in zip(voting_dict[sen_a],voting_dict[sen_b])])
## Task 3
def most_similar(sen, voting_dict):
"""
Input: the last name of a senator, and a dictionary mapping senator names
to lists representing their voting records.
Output: the last name of the senator whose political mindset is most
like the input senator (excluding, of course, the input senator
him/herself). Resolve ties arbitrarily.
Example:
>>> vd = {'Klein': [1,1,1], 'Fox-Epstein': [1,-1,0], 'Ravella': [-1,0,0]}
>>> most_similar('Klein', vd)
'Fox-Epstein'
Note that you can (and are encouraged to) re-use you policy_compare procedure.
"""
max_sen=sen
max_sim=-len(voting_dict[sen])
for x in voting_dict.keys():
if not x==sen:
sim_x=policy_compare(sen, x, voting_dict)
if sim_x>max_sim:
max_sim=sim_x
max_sen=x
return max_sen
## Task 4
def least_similar(sen, voting_dict):
"""
Input: the last name of a senator, and a dictionary mapping senator names
to lists representing their voting records.
Output: the last name of the senator whose political mindset is least like the input
senator.
Example:
>>> vd = {'Klein': [1,1,1], 'Fox-Epstein': [1,-1,0], 'Ravella': [-1,0,0]}
>>> least_similar('Klein', vd)
'Ravella'
"""
min_sen=sen
sim_x=0
min_sim=len(voting_dict[sen])
for x in voting_dict.keys():
if not x==sen:
sim_x=policy_compare(sen, x, voting_dict)
if sim_x<min_sim:
min_sim=sim_x
min_sen=x
return min_sen
## Task 5
most_like_chafee = 'Jeffords'
least_like_santorum = 'Feingold'
# Task 6
def find_average_similarity(sen, sen_set, voting_dict):
"""
Input: the name of a senator, a set of senator names, and a voting dictionary.
Output: the average dot-product between sen and those in sen_set.
Example:
>>> vd = {'Klein': [1,1,1], 'Fox-Epstein': [1,-1,0], 'Ravella': [-1,0,0]}
>>> find_average_similarity('Klein', {'Fox-Epstein','Ravella'}, vd)
-0.5
"""
sum=0
for x in sen_set:
sum+=policy_compare(sen, x, voting_dict)
return sum/len(sen_set)
most_average_Democrat = 'Smith' # give the last name (or code that computes the last name)
# Task 7
def find_average_record(sen_set, voting_dict):
"""
Input: a set of last names, a voting dictionary
Output: a vector containing the average components of the voting records
of the senators in the input set
Example:
>>> voting_dict = {'Klein': [-1,0,1], 'Fox-Epstein': [-1,-1,-1], 'Ravella': [0,0,1]}
>>> find_average_record({'Fox-Epstein','Ravella'}, voting_dict)
[-0.5, -0.5, 0.0]
"""
t=[]
tmp=sen_set.pop()
sen_set=sen_set|{tmp}
for x in range(len(voting_dict[tmp])):
t.append(sum([voting_dict[y][x]for y in sen_set])/len(sen_set))
return t
#voting_dict=create_voting_dict()
#democrats=[x.split()[0] for x in voting_data if x.split()[1]=='D']
#average_Democrat_record = set(find_average_record(democrats, voting_dict))
average_Democrat_record = [-0.16279069767441862, -0.23255813953488372, 1.0, 0.8372093023255814, 0.9767441860465116, -0.13953488372093023, -0.9534883720930233, 0.813953488372093, 0.9767441860465116, 0.9767441860465116, 0.9069767441860465, 0.7674418604651163, 0.6744186046511628, 0.9767441860465116, -0.5116279069767442, 0.9302325581395349, 0.9534883720930233, 0.9767441860465116, -0.3953488372093023, 0.9767441860465116, 1.0, 1.0, 1.0, 0.9534883720930233, -0.4883720930232558, 1.0, -0.32558139534883723, -0.06976744186046512, 0.9767441860465116, 0.8604651162790697, 0.9767441860465116, 0.9767441860465116, 1.0, 1.0, 0.9767441860465116, -0.3488372093023256, 0.9767441860465116, -0.4883720930232558, 0.23255813953488372, 0.8837209302325582, 0.4418604651162791, 0.9069767441860465, -0.9069767441860465, 1.0, 0.9069767441860465, -0.3023255813953488] # (give the vector)
# average_Democrat_record = [-0.162791, -0.232558, 1.000000, 0.837209, 0.976744, -0.139535, -0.953488, 0.813953, 0.976744, 0.976744, 0.906977, 0.767442, 0.674419, 0.976744, -0.511628, 0.930233, 0.953488, 0.976744, -0.395349, 0.976744, 1.000000, 1.000000, 1.000000, 0.953488, -0.488372, 1.000000, -0.325581, -0.069767, 0.976744, 0.860465, 0.976744, 0.976744, 1.000000, 1.000000, 0.976744, -0.348837, 0.976744, -0.488372, 0.232558, 0.883721, 0.441860, 0.906977, -0.906977, 1.000000, 0.906977, -0.302326]
# Task 8
def bitter_rivals(voting_dict):
"""
Input: a dictionary mapping senator names to lists representing
their voting records
Output: a tuple containing the two senators who most strongly
disagree with one another.
Example:
>>> voting_dict = {'Klein': [-1,0,1], 'Fox-Epstein': [-1,-1,-1], 'Ravella': [0,0,1]}
>>> bitter_rivals(voting_dict)
('Fox-Epstein', 'Ravella')
"""
tx=0
ty=0
sums=len(voting_dict[list(voting_dict.keys())[0]])
for x in voting_dict.keys():
y=least_similar(x, voting_dict)
min_s=policy_compare(x, y, voting_dict)
if min_s<sums:
sums=min_s
tx=x
ty=y
return (tx, ty)