# OK to post homework
# Joseph Koutsoutis, 02-04-2024, Assignment 4

#1

# Here are some small examples based on pages 91-end
# of Frank Garvan's awesome Maple booklet

#for i from 2 by 3 to 11 do print(i): od:

#i := 2:
#while i <= 11 do:
# print(i): i += 3:
#od:
#i := 'i':

#for i in [2,5,8,11] do print(i): od:

#f := proc(x)
# RETURN(sqrt(x^3 - x + 1)):
#end:
#g := proc(x)
# RETURN(-f(x)):
#end:
#with(plots):
#p1 := plot(f,-2..2):
#p2 := plot(g,-2..2):
#display(p1, p2);

#2

# Here are my initials in a 5x11 matrix:

# 00001001001
# 00001001010
# 00001001100
# 10001001010
# 01110001001

# and here is the one dimensional form of this vector:

# 0000100100100001001010000010011001000100101001110001001

#3

#These 3 functions were written in C4.txt:
HD:=proc(u,v) local i,co:
co:=0:
for i from 1 to nops(u) 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:


#RCBestLTrials(L) runs RC(q,n,d,K) for
#each combination of values with q=2, K=10000,
#5 <= n <= 16, d in {3,5,7} a total of L times and
#records the largest value of M returned.
RCBestLTrials:=proc(L) local q,n,d,K,i,M:
q := 2:
K := 10000:
for d in [3,5,7] do:
 for n from 5 to 16 do:
  M := 0:
  for i from 1 to L do:
   M := max(M, nops(RC(q,n,d,K))):
  od:
  print(sprintf(`M=%d was the best result for q=2,n=%d,d=%d`, M, n, d)):
 od:
od:
end:

#Here are my results in the form of a table after running RCBestLTrials(5):

# n    d=3    d=5    d=7
# 5      4      2      1
# 6      8      2      1
# 7     11      2      2
# 8     18      4      2
# 9     30      6      2
#10     53      9      2
#11     90     13      4
#12    158     21      4
#13    275     30      6
#14    451     46     11
#15    749     71     14
#16   1216    107     20

#Generally, RC only performed well for small values of n, but after this, 
#RC only found codes of around half the optimal size.


#4

# Let n = 2^r - 1 and d = 3.
# Since binary Hamming codes are perfect, the size of the code 
# matches the sphere packing bound.
# We compute:
# M = 2^n / (binom(n,0) + binom(n,1))
#   = 2^n / (1 + n)
#   = 2^n / (2^r)
#   = 2^(n - r).