# OK to post homework
# Alex Varjabedian, 4-Feb-2024, Homework 4

Help := proc() print(`HC(u, v)\nRC(q, n, d, K)\nrunRCs()\nSPB(q, n, t)\nSPBsimplified(n)`) end:
with(linalg):

###########################
# ----------------------- #
# PART 1 - Maple Examples #
# ----------------------- #
###########################

print(`PART 1`);

# 7.3 - Elementary row operations

A := matrix(3, 4, [1, 1, 3, -3, 5, 5, 13, -7, 3, 1, 7, -11]);
A1 := addrow(A, 1, 2, -5);
A2 := mulrow(A1, 3, -1/2);

# 7.4 - Gaussian elimination

gausselim(A);
gaussjord(A);

# 7.5 - Inverses and determinants

A := matrix(3, 3, [1, 1, 3, 5, 5, 13, 3, 1, 17]):
det(A);
B := inverse(A);

# 7.6 - Row space, column space, nullspace

rank(A);
rowspace(A);
colspace(A);
nullspace(A);

# 7.7 - Eigenvectors and diagonalization
eigenvals(A);
eigenvects(A);
eigenvals(B);
eigenvects(B);

#############################
# ------------------------- #
# PART 2 - Drawing Initials #
# ------------------------- #
#############################

initials := matrix(11, 29, [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]);

initials_vector := []:
for i from 1 to 11 do
 for j from 1 to 29 do
  initials_vector := [op(initials_vector), initials[i, j]]:
 od:
od:
initials_vector := initials_vector;

###########################
# ----------------------- #
# PART 3 - Best RC Values #
# ----------------------- #
###########################

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)
[seq(rand(0..q-1)(), 1..n)]:
end:

RC := proc(q, n, d, K) local C, v, i, c:
C := {}:
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:

# Runs RC 5 times, given n and d
doRC := proc(n, d) local count, i:
count := 0:
for i from 1 to 3 do count := max(count, nops(RC(2, n, d, 10000))) od:
count:
end:

runRCs := proc() local i, results3, results5, results7:
# For d = 3
print(`For d = 3 and n from 5 to 16`);
results3 := []:
for i from 5 to 16 do results3 := [op(results3), doRC(i, 3)] od:
print(results3);
# For d = 5
print(`For d = 5 and n from 5 to 16`);
results5 := []:
for i from 5 to 16 do results5 := [op(results5), doRC(i, 5)] od:
print(results5);
# For d = 7
print(`For d = 7 and n from 5 to 16`);
results7 := []:
for i from 5 to 16 do results7 := [op(results7), doRC(i, 7)] od:
print(results7);
end:

# Call runRCs() to see the results
print(`After calling runRCs(), which takes a very long time, the results are as follows:`);
print(`For d = 3 and n from 5 to 16`);\
print([4, 6, 10, 17, 30, 51, 90, 158, 271, 449, 749, 1215]);
print(`For d = 5 and n from 5 to 16`);
print([2, 2, 2, 4, 6, 9, 12, 21, 29, 43, 69, 108]);
print(`For d = 7 and n from 5 to 16`);
print([1, 1, 2, 2, 2, 2, 4, 4, 6, 8, 13, 17]);
print(`I noticed that, for lower values of n, my values were closer to the best values. However, for larger values of n, my values were not even close to the best values. I would probably be closer to the best values if I ran RC more times, but that would take hours to finish executing.`);

#################################
# ----------------------------- #
# PART 4 - Binary Hamming Codes #
# ----------------------------- #
#################################

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

# Since d = 2t + 1 = 3, we know that t = 1. We also know that q = 2. So, we can simplify the Sphere Packing Bound equation as follows.
# q^n/add(binomial(n, i)*(q-1)^i, i = 0..t) = 2^n/add(binomial(n, i)*(2-1)^i, i = 0..1) = 2^n/(binomial(n, 0) + binomial(n, 1)) = 2^n/(1+n)
# We can write a new procedure and compare results for n = 2^r - 1

SPBsimplified := proc(n) 2^n / (1 + n) end:

for r from 1 to 8 do printf("SPB: %d          SPBsimplified: %d\n", SPB(2, 2^r - 1, 1), SPBsimplified(2^r - 1)) od: