#OK to post homework
#GLORIA LIU, Feb 4 2024, Assignment 4

#=====================================#
#1. Read and do all the examples, plus make up similar ones, in pages 91-end of Frank Garvan's awesome Maple booklet
#Chapter 7
with(linalg):
A:=matrix(3,3,[1,1,3,5,5,13,3,1,7]):
rank(A):
eigvects(A):
A:randommatrix(3,3):
A:='A':

#Chapter 8
g:=proc(x,y) local z,i:
global v,w:
if x*y > 1 then
 v:=x+y:
else
 w:=x-y:
fi:
x*y:
end:

#=====================================#
#2. Inspired by Exercise 1.1 of Raymond Hill's book (p. 10) (there is an answer at the end of the book) form a matrix with 0-1 whose number of rows and number of columns are both prime numbers and "draw" your initials (in my case e.g. DZ) such that the 1's will show it. (and the 0-th are the background). Then turn it into a 1-dimensional vector.

#1 1 1 1 1 0 0 1 0 0 0 0 0
#1 0 0 0 1 0 0 1 0 0 0 0 0
#1 0 0 0 0 0 0 1 0 0 0 0 0
#1 0 0 0 0 0 0 1 0 0 0 0 0
#1 0 0 0 0 0 0 1 0 0 0 0 0
#1 0 0 0 0 0 0 1 0 0 0 0 0
#1 0 0 1 1 1 0 1 0 0 0 0 0
#1 0 0 0 1 0 0 1 0 0 0 0 0
#1 0 0 0 1 0 0 1 0 0 0 0 0
#1 0 0 0 1 0 0 1 0 0 0 0 0
#1 1 1 1 1 0 0 1 1 1 1 1 1

#1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1

#=====================================#
#3. Uee RC(q,n,d,K) with q=2, d=3,5,7, and 5 ≤ n ≤16 and K very big (say 10000), and each time run it several times and pick the one with the most elements (to get M as big as possible). How do the codes that you got compare to the best possible values in table 2.4 on p.14 of Hill's book?

#Copying the functions
HD:=proc(u,v) local i,co:
co:=0:
for i from 1 to nops(v) do
 if u[i]<>v[i] then
  co:=co+1:
 fi:
od:
co:
end:

RV:=proc(q,n) local ra,i:
ra:=rand(0..q-1):
[seq(ra(), i=1..n)]:
end:

RC:=proc(q,n,d,K) local C,v,i,c:
C:={RV(q,n)}:
for i from 1 to K do
 v:=RV(q,n):
 if min(seq(HD(v,c), c in C))>=d then
  C:=C union {v}:
 fi:
od:
C:
end:

for d from 1 to 3 do
 d1:=d*2 + 1:
 for n from 5 to 16 do
  maximum:=0:
  for t from 1 to 5 do
   #print(RC(2,n,d1,10000));
   maximum:=max(maximum, nops(RC(2,n,d1,10000))):
  od:
  print(d1, n, maximum);
 od:
od:

#Results:
#  n  |d = 3|d = 5|d = 7
#-----------------------
# 5   |4    |2    |1    
# 6   |8    |2    |1
# 7   |12   |2    |2
# 8   |18   |4    |2
# 9   |30   |6    |2
# 10  |51   |8    |2
# 11  |90   |12   |4
# 12  |155  |19   |4
# 13  |275  |29   |6
# 14  |455  |45   |9
# 15  |753  |69   |14
# 16  |1210 |110  |18

#These results are smaller than the best possible values listed in the book - as n grows larger, the difference between the ideal values and the experimental values here grow larger.

#=====================================#
#4. The binary Hamming codes (to be studied later) have n=2^r-1 (where r is a positive integer), and minimal distance 3. They are known to be perfect. How big are they?

#These perfect Hamming codes will have size 2^(2^r - 1 - r). 
#We can see this from the Sphere packing bound, where M<=trunc(q^n/add(binomial(n,i)*(q-1)^i, i=0..t)), setting q=2, n=2^r-1, and t=1.
#(2^(2^r-1)/add(binomial(n,i)*(q-1)^i, i=0..1) = (2^(2^r-1))/(1+2^r-1)
# = 2^(2^r - 1 - r). 

SPB:=proc(q,n,t) local i:
trunc(q^n/add(binomial(n,i)*(q-1)^i,i=0..t)):
end:
SPB(2,7,1);
SPB(2,15,1);
SPB(2,31,1);