#OK to Post

#RUN AT YOUR OWN RISK: 3-5 ARE VERY SLOW 

#1: [For everyone] Read and understand Chapter 2 of Hill's book. Do #human exercises 2.1,2.2,2.3,2.4

#2.1: (6,2,6): we want 2 words of length 6 with min distance 6: these #are (0,0,0,0,0,0), (1,1,1,1,1,1). 

# (3,8,1): 8 words of length 3 with min distance 1. There are 8 words #of length 3, so this is just all the binary words of length 3

#(4,8,2): 8 words of length 4 with min distance 2: 0000, 1100, 0011, #1111, 1010, 0101, 1001, 0110. 

#(5,3,4): 3 words of length 5 with min distance 4: not possible. #suppose there exist 3 words of length 5 with minimum distance 4. The #first two must differ in 4 positions. Suppose the third agrees with #the first in one position, without loss of generality. Then it must #disagree with the first in all other positions. However, if the #second also disagrees with the first in 4 positions, then the third #word differs from the second in at most 3 places, contradicting that #the min distance is 4. 

#(8,30,3): We want 30 words of length 8 with minimum distance 3. #Consider non-overlapping spheres of radius 1 (if we considered radius #2 we would have to allow overlapping spheres). Since any vector has 8 #radius-1 neighbors, there must be 9*30=270 binary vectors of length #8,but there are only 2^8=256 of them.  We conclude that a (8,30,3) #code does not exist. 


#2.2:The claim is that we can shorten the lengths of the words in a #code by 1 and keep at least half of the words in the code. Given a #(n,M,d) code, we cut off the last entry of each word. Consider the #binary tree. At level n of the tree, each node corresponds to a #binary word of length n. By cutting off the last entry of each word #in a code, we "prune" the last level of the tree. The number of words #which are at minimum distance d from words of length n is represented #by the number of words at the n-d level of the tree. Therefore, the #number of words at the n-1 level (words after the last element has #been removed) with minimum distance d is the number of words at the #n-1-d level on the tree, which is half of n-d. We conclude that there #exists a binary (n-1,M', d) code with M'>=M/2. 

#2.3: Observe first that A_q(3,2) is at least q^2: Suppose we have a #q-ary code where each word is of length 3 and the minimum distance is #2. By removing the last letter of all the words, we obtain q^2 #distinct words of length 2, or else the minimum distance wasn't 2. 
#Moreover, A_q(3,2) is at most q^2: suppose FSOC there is a code of #size q^2+1 satisfying our initial conditions. We can make at most q^2 #distinct words of length 2 (minimum distance 1). Suppose there is a #(q^2+1)th word. Then such a word must have the same first two letters #as some other word, breaking the requirement that the minimum #distance between any two words be 2. 

#2.4:Consider the set of 0-1 vectors of length n-1. Given any vector #in this set, if the sum of its entries is 0 mod 2, add a 0 to the #end, making a vector of length n. If the sum of its entries is 1 mod #2, add a 1 to the end, making a vector of length n. That is, the set #of all length n even-weight vectors is a mininmum-distance-2 code, #because all vectors in our set of 0-1 vectors were distinct, and we #append either 0 or 1 (NOT both-separately) to each vector of length #n-1. Furthermore, there are 2^{n-1} words in the code, corresponding #to the number of binary vectors of length n-1 (as before, for each #vector of length n-1, there is a unique vector of length n in our #set). Thus E_n is a (n, 2^{n-1}, 2)-code. 

#______________________________________________


#2: [For everyone] Read and understand Chapters 3 and 4 of Hill's #book. Most people should be familar with this material from abstract #algebra and linear algebra classes (note that the linear algebra is #the same, but over a finite field) DONE

#______________________________________________


#3:[For everyone] Use GRC(q,n,d) with q=2, d=3,5,7, and 5 ≤ n ≤20, for #each case find the cardinality of the code (what's called M in the #book). Also find the Sphere-Packing Bound. How far are they in each #case?

#Alphabet {0,1,...q-1}, Fqn(q,n): {0,1,...,q-1}^n
Fqn:=proc(q,n) local S,a,v:
option remember:
if n=0 then
 RETURN({[]}):
fi:

S:=Fqn(q,n-1):

{seq(seq([op(v),a],a=0..q-1), v in S)}:

end:


#SPB(q,n,d): The best you can hope for (as far as the size of C) for q-ary (n,2*t+1) code
SPB:=proc(q,n,t) local i:
trunc(q^n/add(binomial(n,i)*(q-1)^i,i=0..t)):
end:

#Nei(q,c): all the neighbors of the vector c in Fqn(q,n)
Nei:=proc(q,c) local n,i,a: 
n:=nops(c):
{seq(seq([op(1..i-1,c),a,op(i+1..n,c)], a=0..q-1) , i=1..n)}:
end:

#SP(q,c,t): the set of all vectors in Fqn(q,n) whose distance is <=t from c
SP:=proc(q,c,t) local S,s,i:
S:={c}:
for i from 1 to t do
 S:=S union {seq(op(Nei(q,s)),s in S)}:
od:
S:
end:

GRC:=proc(q,n,d) local S,A,v:
A:=Fqn(q,n):
S:={}:
while A<>{} do:
 v:=A[1]:
 S:=S union {v}:
 A:=A minus SP(q,v,d-1):
od:
S:
end:

for n from 5 to 7 do:
GRC(2,n,3);
SPB(2,n,3);
print('c');
GRC(2,n,5);
SPB(2,n,5);
print('c');
GRC(2,n,7);
SPB(2,n,7);
print('c');
od:


#______________________________________________

#4: [For everyone] Use GRC(q,n,d) with q=3, d=3,5,7, and 5 ≤ n ≤10, for #each case find the cardinality of the code (what's called M in the #book). Also find the Sphere-Packing Bound. How far are they in each #case?

for n from 5 to 10 do:
GRC(3,n,3);
SPB(3,n,3);
print('c');
GRC(3,n,5);
SPB(3,n,5);
print('c');
GRC(3,n,7);
SPB(3,n,7);
print('c');
od:

#______________________________________________


#5: [For everyone] USe GRC(q,n,d) with q=5, d=3,5,7, and 5 ≤ n ≤7, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

for n from 5 to 7 do:
GRC(5,n,3);
SPB(5,n,3);
print('c');
GRC(5,n,5);
SPB(5,n,5);
print('c');
GRC(5,n,7);
SPB(5,n,7);
print('c');
od:

#run time too long on 3-5. Haven't found a better algorithm



#______________________________________________


#6: [Mandatory for experts, optional but strongly recommended for #novices] Write a procedure ParaBD(BD,v), that inputs a potential #block design with v varieties (or points) (i.e. the universal set is #{1, ..., v}) and checks whether it is indeed a block design (if it is #not it should return FAIL). If it is the output should be the 5-tuple
#[b,v,r,k,lambda]

#(see the bottom of p. 21) Check your program with the following
#ParaBD(BDfano(),7); and ParaBD(BDex212(),11);


ParaBD:=proc(BD,V) local X, S, Cardin, i,n,T,k,a,b,K,set,Bird, set2:

#Checking 1
Cardin:={seq(nops(S),S in BD)};
#converting the multiset of cardinalities to a set
set:=convert(Cardin, set);
if nops(set)=1 
 return(same);
else
 return (FAIL);
fi:

#Checking 2
n:=nops(V);
T:=[seq(0, 1..n)];
for S in BD do
 for i in S do
   T[i]:=T[i]+1
od;
od;
return T;
for i from 1 to nops(T) do:
 print(i, "is a member of", T[i], "sets");
od;

for k from 2 to n do
 if T[1]<>T[k]
 return(FAIL);
else 
 return(same);
fi:
od:

#Checking 3

K:=[seq(0, 1..n)];
for S in BD do
for a from 1 to n do
 for b from 1 to n do
if a in S and b in S
 K[(a,b)]:=K[(a,b)]+1;
fi:
od:
od:
Bird:={seq(nops(K[(a,b)]))};
set2:=convert(Bird, set);
if nops(set2)=1 
 return(same);
else
 return (FAIL);
fi:
od:


end:





#______________________________________________
#7: [For everyone]
#Using Ex. 2.20 (p. 29) write a procedure
#PlotkinBound(n,d) For binary codes. For all d from 2 to 20 and n from #2 to 2d find which is bigger, the Sphere-Packing bound or the Plotkin #bound?


#PlotkinBound(n,d): 
PlotkinBound:=proc(n,d) local j:
j:=(2*d)/(2*d-n);
return(j);
end:


#Comparison(n,d):
Comp:=proc(n,d) local k:
k:=PlotkinBound(n,d)-SPB(2,n,d);
print(k);
end:

#If Comp is positive, the Plotkin bound is higher and thus SPB is #better. If Comp is negative, the SPB bound is higher and thus Plotkin #is better as an upper bound. 

#The loop: 
for d from 2 to 20 do;
  for n from 2 to 2*d-1 do;
  print("iteration with n =", n, "and d =", d);
    Comp(n,d);
od:
od:


#______________________________________________