Math 640: EXPERIMENTAL MATHEMATICS (Automated Guessing and Proving and Introduction to Machine Learning) Spring 2019 (Rutgers University)
http://sites.math.rutgers.edu/~zeilberg/math640_19.html
Last Update: May 22, 2019.
Additional Texts
Description
Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction.
In addition to learning the philosophy and methodology of this budding field, students will become computeralgebra wizards,
and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.
We will first learn Maple, and how to program with it. This semester we will learn the foundation of experimentalsymbolic
mathematics using the excellent book `The Concrete Tetrahedron' by Manuel Kauers and Peter Paule. An Ebook will be
downloadable to each registered student, free of charge, (by kind permission of the authors).
[Of course, everyone is welcome to buy a print version.]
We will also learn the basics of machine learning, and relate it to experimental mathematics.
Optional (but Highly recommended) Getting Started Homework
Teach yourself the basics of Maple by reading Frank Garvan's goldenoldie
part 1,
part 2
Note: a few commands are no longer valid in today's Maple. The
most important one is that " has been replaced by %.
For more details, see this 2002 masterpiece.
How to submit homework

Every class has a homework assignment. Both Mondays and Thursdays' are due
10:00pm Sunday of the following week.
It should be sent to the email address
ShaloshBEkhad at gmail dot com
Subject: HomeWork#X
and then attach a .txt file(s) called
hwXYourFirstNameYourLastName.txt
where X is the number of the assignment
Except for the first assignment, you should have two attached .txt files.
For example, when Yukun Yao submits homework assignments 2 and 3, he should
email ShaloshBEkhad at gmail dot com, with
Subject: HomeWork#2#3
and attach the text files (the source code plus human comments (such lines must start with #)
hw2YukunYao.txt and hw3YukunYao.txt

The very first line of the .txt files should have
#Please do not post homework
or
#OK to post homework
Followed by
#Your Name, Date, Assignment X
Diary and Homework assignments
Programs done on Thurs., Jan. 24, 2019
C1.txt ,
Contains procedures
Homework for Thurs., Jan. 24, 2019, class (due Sunday Jan. 27, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#1
and an attachment
hw1FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

[People who took this class before, or already know Maple, are exempt from this]
Read and do all the examples, plus make up similar ones,
in the first 30 pages of Frank Garvan's
awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw1YourName.txt .

[For everyone].
Read and understand pp. 112, of the KauersPaule "Concrete Tetrahedron" (in the secret url I told you about. If you forgot, Email me).

[Mandatory for experts, optional for novices]
Write a program QSort(L), that implements quicksort. Use a rand(1..nops(L)) to pick a pivot and recursion.

[Mandatory for experts, optional for novices]
Write a program c(n) that inputs a nonnegative integer and computes the average number of comparisons it takes for Quicksort
when applied to a list of length n, as given in the recursion for c(n) in p. 4 of the book. Check your answer with the table.

[Mandatory for experts, optional for novices]
Write a program c1(n) that uses the formula for the above quantity given at the end of section 1.2 .
Make sure that you get the same thing as the above c(n).
Added Jan. 28, 2019: See the students' nice solutions
Programs done on Monday, Jan. 28, 2019
C2.txt ,
Contains procedures [In addition to those of C1.txt whose Help is now "Help1();" ):

Qs(L): inputs a list of numbers and outputs the sorted list (in increasing order)

TestS(n,K,T,f): Inputs a positive integer n (the length of the list) K (the upper bound)), T
the number of times to run it, and f the function (sort, Qs, SelS).
Outputs the list of running times (sorted, in increasing order) followed by the average.

QsC(L): Line Qs(L) but also returns the number of comparisons

PQs(n,t):the prob. generating function, in t, of the random variable "number of comparisons in quicksort"
Homework for Monday Feb. 4, 2019, class (due Sunday Feb. 10, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#4
and an attachment
hw2FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

[People who took this class before, or already know Maple, are exempt from this]
Read and do all the examples, plus make up similar ones,
pp. 3061 of Frank Garvan's awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw2YourName.txt .

[For everyone]. Read and understand Chapter 1 of the KauersPaule "Concrete Tetrahedron" (in the secret url I told you about. If you forgot, Email me).

[For everyone] (human exercises) Solve problems 1.11.5 at the end of chapter 1 of the book (pp. 1516)
[you can either do it in .txt file, and use Maple notation for mathematical symbol, or handwritten and give it to me in person,
or scan the handwritten answers and email a .pdf]

[Optional Challenge, no peeking, 5 dollars (I don't know the answer)] Find an expression (or efficient algorithm) in terms of n and/or the Harmonic numbers H_{n}
for the variance of the random variable (defined on random lists of n elements) "number of comparisons in quicksort".
[Possible hint: look at the recurrence for PQs(n,t), and apply (t d/dt) twice, using the product rule. Then plugin t=1 and get a recurrence
for the second moment , m_{2}(n) of that random variable, and then use the famous result that the variance is
m_{2}(n)c(n)^{2}].
Added Feb. 4, 2019: See the students' nice solutions
Programs done on Thurs., Jan. 31,, 2019
C3.txt ,
Contains procedure

PQs(n,t):the prob. generating function of the running time of Quicksort
[from C2.txt]

MFtoGF(M, t): inputs a prob. mass function of a finite and discrete prob. dist. given
[ ... [outcome, Pr(outcome)], ...] and a variable name (of type symbol) and outputs
the prob. gen. function

GFtoMF(f,t): inputs a prob. gen. function in the variable t, and outputs the prob. mass function
for a finite discrete prob. dist.
as a list of pairs [outcome, Pr(outcome)]

Moms(f,t,K): inputs a prob. gen. function and outputs the first K moments

MomsAM(f,t,K): inputs a prob. gen. function and outputs the first K moments about the mean
Homework for Thurs. Jan. 31, 2019, class (due Sunday Feb. 3, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#3
and an attachment
hw3FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

[People who took this class before, or already know Maple, are exempt from this]
Read and do all the examples, plus make up similar ones,
pp. 6292 of Frank Garvan's awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw3YourName.txt .

[For everyone]
Read and understand the first five pages of
Dr. Z.'s article
about discrete probability distributions and their continuous limit.

[For experts, but novices are strongly encouraged]
The scaled kth moments of a probability distribution is m_{k}/ (m_{2})^{(k/2)}, where
m_{k} is the kth moment about the mean. Using
MomsAM(f,t,K):
Write a procedure
ScaledMomsAM(f,t,K):
that inputs a probability generating function f (of the variable t), and outputs the first K scaled moments about the mean. The first and second entries
of ScaledMomsAM(f,t,K) should be the mean and variance, but starting at the 3rd it should be the scaled moments.

If you do
ScaledMomsAM(((1+t)/2)^n,t,14)
and take the limits of the third through 14th scaled moment, as n goes to infinity, what do you get?

By applying ScaledMomsAM(f,t,14) to PQs(n,t), for
n=50,60,.., 100 (and if the computer would agree even a little further), estimate the
the limits of the 3rd scaled moment (the skewness) and 4th scaled moment (the kurtosis)
of the random variable "number of comparisons in quicksort applied to a list of length n", as n goes to infinity.

[Challenge, 5 dollars I don't know the answer] Determine the exact values of these limits. Are they expressible in
terms of known constants like Pi, e, and gammma?
Added Feb. 4, 2019: See the students' nice solutions
Programs done on Monday, Feb. 4, 2019
C4.txt ,

GuessPol1(L,n,d): inputs a list of pairs [[input,output], ...] a variable name n
and a pos. integer d, outputs a polynomial of degree d f such that f(input)=output

GuessPol(L,n): inputs a list of pairs [input,output] and tries to guess
a polynomial of degree <=nops(L)3

Comp(n,k): inputs nonneg. integers n and k and outputs the SET of
compositions of n into k parts (vectors of nonneg. integers that addup to n)
of length k
Homework for Feb. 4, 2019 class (due Sunday Feb. 10, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#4
and an attachment
hw4FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

[People who took this class before, or already know Maple, are exempt from this]
Read and do all the examples, plus make up similar ones,
pp. 93 to the end of Frank Garvan's awesome Maple booklet
(
part 1,
part 2)
Only record a small sample in hw4FirstNameLastName.txt .

[modified Feb. 5, 2019, thanks to Jason Saied (who won a dollar)]
What we called compositions in class was not not the usual kind. In the usual kind all
the entries are strictly positive. Let's call the usual kind strict compositions.
First tweak the program Comp(n,k) to write a procedure SComp(n,k) that
outputs the set of strict compositions of n into k parts.
Then write a program, c(n,k), that just outputs the number of elements in SComp(n,k).
Of course, procedure c(n,k) should me much faster (for large n and k) than doing nops(SComp(n,k)).

By using GuessPol, find explicit expression for c(n,k) for k=2..10. Can you guess a general expression for
c(n,k) for general k?

[Human exercise] Can you prove your guess?

[Human and/or machine exercise]
Can you conjecture a closedform formula for the total number of compositions of n, i.e.
c(n,1)+ ...+ c(n,n) ?
Can you prove it?
Added Feb. 11, 2019: See the students' nice solutions
Programs done on Thursday, Feb. 7, 2019
C5.txt
contains all the procedures of C4.txt (listed in Help4(); ) as well as the following new procedures

PreMag(a,b,n):inputs nonneg. integers n,a,b, and outputs the set of a by b matrices (given as lists of lists) with nonnegative entries and row sums n,

IsMagic(A,k): inputs a matrix A and outputs true iff all the columns of A addup to k

MagRec(a,b,n): the set of a by b matrices with nonneg. entries such that every row sum is n and every column sum a*n/b
Homework for Feb. 7, 2019 class (due Sunday Feb. 10, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#5
and an attachment
hw5FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Read and understand sections 2.1, 2.2, and 2.3 (pp. 1728)

[Modified Feb.10, 2019, 7:20am, thanks to Victoria Chayes]
It can be shown (you are welcome to do it, but it is not part of the problem) that
the number of k by 2 magic rectangles with column sums all n
(and the row sums equaling n*k/2) is
the coefficient of x^(n*k/2) in (1+x+...+x^n)^k .
[ if n*k is even, it is 0 if both n and k are odd]
Using the maple command "expand" and "coeff" write a oneline procedure
M2(k,n)
that inputs k and n and outputs this number.

Using this procedure, guess polynomial expressions for
M2(2,n), M2(4,n),M2(6,n),M2(8,n), M2(10,n),
M2(3,2n),M2(5,2n), M2(7,2n), M2(9,2n)
Which ones of them are in the OEIS?
Added Feb. 11, 2019: See the students' nice solutions
Programs done on Monday, Feb. 11, 2019
C6.txt
contains all the procedures of C4.txt and C5.txt (listed in Help4(); and Help5();) as well as the following new procedures

NuM(A,k,c):The number of vectors of length k whose components are
members of A that addup to c. For example the number of 3 by 3 magic squares
with row sums and column sums all equal to 5 is NuM(Comp(5,3),3,[5,5,5]);

GFpowe(x,k): The generating function of the discrete function n^k

Delt(L): inputs a list L and outputs a list of L[i+1]L[i]
Special Challenge for Feb. 11, 2019 class (due Wed. Feb. 13, 10:00pm)
Make up a problem (using Maple) whose answer is appropriate for Valentine Day.
The proposer of the best problem will get a chocolate box.
Note: to get some ideas you can look at previous editions of this class.
All the problems will be made public on Feb. 14, and then there would be another contest (due Sunday, Feb. 17, 10:00pm, same as the homework)
for solving them (of course the proposer can't participate in the problem that they created).
Please email ShaloshBEkhad at gmail dot com an email with
Subject: VD problem, and two attachments
vdProblemFirstNameLastName.txt (or vdProblemFirstNameLastName.pdf) and
vdSolutionFirstNameLastName.txt (or vdSolutionFirstNameLastName.pdf) that includes BOTH problem and solution
(with your name)
Added Feb. 14, 2019: Here are students' interesting
proposed problems.
Homework for Feb. 11, 2019 class (due Sunday Feb. 17, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#6
and an attachment
hw6FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

[Corrected, thanks to Songhao Zhu]
A quasipolynomial sequence of period m is a sequence such that for each congruence class mod m, is given
by a polynomial. In other words, there exist m polynomials P1(n), ..., Pm(n) such that
L[n]=Pi(n) is n is i ( mod m)
[For the sake of convenience we let P0(n) be called Pm(n)]
The data structure that we will use to describe a quasipolynomial of period m is a list of polynomials
[P1(n), ..., Pm(n)]
(once you have it, its period is gotten simply by doing nops)
Write a procedure GuessQuasiPol1(L,n,m) that inputs a list L, of values (starting at its value at 1, so unlike our GuessPol the input is a list
of numbers NOT a list of pairs [input,output]), and a pos. integer m, and guesses a quasipolynomial of period m.
You can use GuessPol as a subprocedure.It should return FAIL if it fails.

Using GuessQuasiPol1(L,n,m), write a procedure GuessQuasiPol(L,n,M) that guesses a quasipolynomial of period<=M or returns FAIL.

Write a procedure
FunTSeq(f,x,N)
that inputs an explicit expression (for example, a rational function, but not only) and outputs the first N terms of its Taylor expansion
around x=0, starting with n=1.
[Hint: use the commands taylor and coeff]

The generating function for the number of (integer) partitions of n into at most k parts, p_k(n) is, famously
Sum(p_k(n)*q^n,n=0..infinity)= 1/((1q)(1q^2) ... (1q^k))
Write a procedure
Park(k,N) that inputs a pos. integer k and a much larger pos. integer N and outputs the first N terms of the sequence
"number of partitions with at most k parts"

Conjecture quasipolynomial expressions for Park(k,N) for k=2,3,4 (and if you are brave, larger)
Added Feb. 17, 2019: See the students' nice solutions
Programs done on Thursday, Feb. 14, 2019
C7.txt

Comp(n,k): inputs nonneg. integers n and k and outputs the SET of
compositions of n into k parts (vectors of nonneg. integers that addup to n)
of length k
[stolen from C4.txt]

GuessMulPol1(L,x,k,d): inputs a list L of data of the form [pt,value] where
pt is a list of length k, and value is the value. Guesses a polynomial
in x[1], ..., x[k] of degree d,P, such that P(L[i][1])=L[i][2]
[slightly modified after class to exclude the zero polynomial in case all the outputs are 0]

GuessMulPol(L,x,k): like GuessMulPol1(L,x,k,d) but with no degree restriction (except for the size of the data set.
[Added after class ended]
Homework for Feb. 14, 2019 class (due Sunday Feb. 17, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#7
and an attachment
hw7FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Either using Maple's combinat[fibonacci], or making up your own homemade procedure F(n) for the Fibonacci numbers, use
GuessMulPol(L,x,k) [added by Dr. Z. after class] to conjecture a polynomial of two variables, P(x,y), such that
P( F_{n}, F_{n+1})=0

Read and understand pp. 36 of this
masterpiece
Added Feb. 17, 2019: See the students' nice solutions
OPTIONAL Valentine Day's Problem Solving Contest (due Sunday Feb. 17, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: VD
and an attachment
vdSolutionsFirstNameLastName.txt
and solve as many of the problems in
here
all in the same file.
The best solver will get a chocolate box.
Added Feb. 17, 2019: Yukun Yao solved all the problems and he gets the prize.
The proposers' solutions of their problems have been added.
Programs done on Monday, Feb. 18, 2019
C8.txt
Contains the following new procedures:

CtoSeq(C,N): inputs a Cfinite sequence C=[INI,Rec] and a pos. integer N and
outputs the first N terms starting at n=0

GuessPolC(C,N,x,r): Inputs a Cfinite sequence C=[INI,Rec] (denoting a sequence of order k, say)
k=nops(INI) and a(n)=Rec[1]*a[n1]+ ... + Rec[k]*a[nk] . Fib is [[0,1],[1,1]]
and outputs a polynomial P, in x[1], ..., x[r], such that P(a(i),...,a(i+r1))==0
N is the number of data gathered
Homework for Feb. 18, 2019 class (due Sunday Feb. 24, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#8
and an attachment
hw8FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Write a program A(n) that inputs a nonnegative integer n and outputs the set of compositions of n whose entries are in the set {1,2}.
For example A(2) should output {[1,1],[2]}. Convince yourself that nops(A(n))=fibonacci(n+1).

Read and understand this
masterpiece by Michael Werman and some other person,
and write Maple programs that implement both sides of the bijection:
pi(C1,C2) piInv(C1,C2) that input pairs of such Fibonacci compositions (of the right sum, and outputs FAIL if bad input).
[Correction to what I said in class: it turns out that I was not "your age". It was submitted in 1984, when I was 34 years old, sorry
for implying that you are ten years older than you really are]

Write a program SeqToC(L) that inputs a sequence L and tries to guess a Cfinite desciption of it C=[INI,Rec]. In other words
the reverse of SeqToC(C,N). Hint: First write SeqToC1(L,d) that looks for a linear recurrence with constant coefficients of order d
(i.e. the size of INI and Rec is d. Make sure that L is at least of length 2d+4. If none found it would return FAIL.]

Using both CtoSeq and your SeqToC, write a Cfinite "calculator", i.e. procedures
AddC(C1,C2) and MulC(C1,C2)
that inputs pairs of Cfinite sequences C1, C2, and outputs the Cfinite description of their sum and product.

[Optional Challenge, I don't know the answer, 5 dollars to the first solver]
It is pretty fast to derive a polynomial relationship generalizing from Fibonacci to sequences satisfying
a(n)=a(n1)+ca(n2)
Just do:
GuessPolC([[0,1],[1,c]],20,x,2);
Also
GuessPolC([[0,1],[2,1]],20,x,2);
produces something nice, but as I hard as I tried, even
GuessPolC([[0,1],[3,1]],200,x,2);
only returned FAIL.
Conjecture: GuessPolC([[0,1],[c,1]],N,x,2);
always returns FAIL except for c=1 and c=2, for any N, in other words, such a polynomial relationship relating a(n) and a(n+1) does not exist,
even of a very high degree.
Added Feb. 24, 2019: See the students' nice solutions
Programs done on Thursday, Feb. 21, 2019
C9.txt
Contains the following new procedures:

PA1(L):
1D perceptron algorithm, PA1(L): inputs a list of pairs [heightIncm,{0,1}] where 0 if she or he did not make it 1 if he or she did
outputs a number c a "predictor" that if x>c then they get to be admitted

ArData(L1,H1,N,c):
inputs L1 and H1 (low and high heights in basketball players and the number N of applicants
and a cutoff c that >=c gets 1 (admitted) and 0 (rejected)

TestP(L,c): Inputs a data set of pairs [height,1 or 0] and a cutoff c, outputs the
triple of false negatives and # of false positive, total number of data entries

NoisyData(L1,H1,N,c,p):
inputs L1 and H1 (low and high heights in basketball players and the number N of applicants
and a cutoff c that >=c gets 1 (admitted) and 0 (rejected) and a prob. p of misclassifying
outputs the noisy data set
Homework for Feb. 21, 2019 class (due Sunday Feb. 24, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#9
and an attachment
hw9FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Read and understand
Section 3.7 of Leslie Valiant's masterpiece.

Generalize ArData(L1,H1,N,c) to an arbitary number of dimensions. Write a procedure but with random points from the ndimensional cube
[0,A]^n . More generally, write a procedure
ArDataMV(A,v,N)
that inputs a pos. number A, and a vector of numbers v (given as a list), (let n:=nops(v))
and outputs a list of length N where each entry is a pair obtained by
picking a random point
(a list of length n) in [A,A]^n and returns the pair [x,0] if v.x (the dot product of v and x) is negative and
[x,1] if it is zero or positive.

Implement the Perceptron algorithm in n dimensions (n arbitrary) by writing a procedure
PAmv(L,n)
that inputs a list containing data of the form [VectorOfLength,ZeroOrOne] where,
VectorOfLengthn is a list of length n, and n is the dimension.

Write an ndimensional extension to TestP(L,c). Call it TestPMV(L,v) where v is a vector (list) with n components.

Added Feb. 22, 2019: Terence Cohelo pointed out, correctly, that the procedure we did in class, PA1(L) is not
the special case of the Perceptron algorithm as described in Valiant's book. Write a procedure
PA1corrected(L)
That first transforms the list L to the format [[data,1],ZeroOrOne], and
uses your procedure PAmv(L,n) with n=2 to
outputs two numbers a and b such that
L[i][2]=1 iff ax+b>=0. Compare its performance to PA1(L).
Added Feb. 24, 2019: See the students' nice solutions
Programs done on Monday, Feb. 25, 2019
C10.txt
Contains the following procedures

[From C8.txt]
Ctoeq(C,N): inputs a Cfinite sequence C=[INI,Rec] and a pos. integer N and
outputs the first N terms starting at n=0.

SeqToC1(L,d) :
inputs a list of numbers (or expressions)
of at least length 2d+4 and and looks for a linear
recurrence with constant coefficients of order d, outputting it in Cfinite description C=[INI,Rec]. Initial conditions are assumed to be the first d terms of the list [from Victoria Chayes' homework hw8.txt]

SeqToC(L) : inputs a list of numbers (or expressions),L, and tries to find a Cfinite description. If it fails, it returns FAIL.
[from Victoria Chayes' homework, hw8.txt]

CtoRat(C,x): inputs a Cfinite sequence [INI,Rec] and a symbol x
outputs the rational generating function of the sequence

RatToSeq(R,x,N): the first N+1 terms of the sequence of coefficients of the rational
function R of x starting at n=0.

GuessAlg1(L,F,x,d): inputs a list of numbers L (starting at n=0)
symbols F and x and a pos. number d, outputs a polynomial P, in F and x
of degree d such that P(x,Sum(L[i+1]*x^i,i=0..nops(L)1) had degree nops(L)
[modified after class to get rid of the annoying factor]

GuessAlg(L,F,x): inputs a list of numbers L (starting at n=0)
symbols F and x and a pos. outputs a polynomial P, in F and x
that fits the data, or else returns FAIL.
Homework for Feb. 25, 2019 class (due Sunday March 3, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#10
and an attachment
hw10FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Read and understand
Dr. Z.'s explanation of procedure CtoRat(C,x)

Read and understand pp. 15 of
Dr. Z.'s essay on enumerative combinatorics
(that appeared in the "Princeton Companion of Mathematics", 2008,edited by T.W. Gowers et. al.)

Using GuessAlg(L,F,x), guess algebraic equations for the sequences
[seq(binomial(m*k,k)/((m1)*k+1),k=0..60)]
For m=2,m=3, m=4, m=5, m=6, m=7 .
Can you guess a metapattern, in terms of m?

[Optional challenge] Can you prove your guess from the last problem at least for m=2, and if possible for general m?
Hint: Use the Lagrange Inversion Formula

Write a procedure
DiagToSeq(f,x,y,N)
that inputs a rational function f in the variables x and y (i.e. a quotient of two polynomials in x,y) whose denominator is not 0 at x=0,y=0
(i.e. it does not blowup at the origin) and returns the first N+1 terms (starting at n=0) of the coefficient of x^{n} y^{n}.
For example
DiagToSeq(1/(1xy),x,y,3);
should return the list [1,2,6,20] .
[Hint, use mtaylor, or better still, use the "taylor" command twice, first w.r.t. to x, and then w.r.t. to y.]

Using DiagToSeq(f,x,y,N) that you wrote (for large enough N) and GuessAlg(L,F,x), that we wrote in class, conjecture algebraic equations for
the diagonal sequences of the following rational functions in x and y
1/(1xy), 1/(1xy+2*x*y), 1/(1x^2y^2+x*y), 1/(1x2*y+3*x*y+x^2+3*y^2) .
Added March 4, 2019: See the students' nice solutions
Programs done on Thursday, Feb. 28, 2019
C11.txt
Contains the following procedures

Trunc(f,x,N): inputs a polynomial f in x and a pos. integer N, outputs the truncation up to x^N

AlgToSeq(INI,Q,x,F,N):
Inputs a poly INI in x alone and a poly Q(F,x) of F and x
and a pos. integer N, output the N+1 coefficients of the unique f.p.s. solution of
f(x)=INI(x)+Q(f(x),x)

MakeNice(P,x,F): converts the equation P(x,F)=0 to the equivalent form
FINI(x)Q(F,x)=P(F,x). Returns [INI,Q]
[corrected after class]
Homework for Feb. 28, 2019 class (due Sunday March 3, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#11
and an attachment
hw11FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Let an algebraic sequence be coded by the 4tuple [INI,Q,F,x], where x and F are symbols, INI is a polynomial in x and
Q is a polynomial in x and F, such that procedure AlgToSeq(INI,Q,x,F,N) returns the first N+1 coefficients.
Interface MakeNice (corrected after class) and GuessAlg(L,F,x) from C10.txt to write a program
GuessNiceAlg(L,F,x) that outputs the quadruple [INI,Q,F,x].

By using AlgToSeq(INI,Q,x,F,N) for sufficiently large N write an "algebraic sequecne calculator" i.e
AddA(A1,A2,N) and MulA(A1,A2,N)
that input algebraic sequences A1, A2 (in the [INI,Q,F,x] data structure) and outputs such representations for their
sum and product, respectively.
Added March 4, 2019: See the students' nice solutions
Programs done on Monday, March 4 2019 , "virtual" class
C12.txt
Contains the following procedures
Homework for March 4, 2019 "class" (due Sunday March 10, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#12
and an attachment
hw12FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

Read and understand the Maple code contained in C12.txt

Write a procedure
DefSum(F,n,k,N)
that inputs an expression in n and k, and outputs the first N terms of the sequence
add(subs({n=n1,k=k1},F), k1=0..n1)
For example,
DefSum(binomial(n,k),n,k,5);
should return
[2,4,8,16,32]

The famous
Zeilberger's algorithm
promises that for any product of binomial coefficients, that contain binomial(n,k) in it
the sequence is Precursive. Since we know it does, it is stupid to use it, let's just guess it.
Using DefSum that you wrote above, write a program
BinToP(F,k,n,N,MaxC)
that inputs an expression F in n and k, a positive integer N, and guesses a recurrence (Precursive description) with maximum complexity
for the
Sum(F(n,k)*binomial(n,k),k=0..n)
What are BinToP(binomial(n,k)^r,k,n,N,10) for r from 0 to 5?
What are
BinToP(binomial(n+k,k),k,n,100,10) , BinToP(binomial(n,k)*binomial(n+k,k),k,n,100,10) , BinToP(binomial(n,k)*binomial(n+k,k)^2,k,n,100,10) ?

Write a procedure
PtoSeq(P,N)
that inputs a Precursive description of the sequence and outputs the first N terms of the sequence. For example
PtoSeq([[1],[n,[1,n]],6);
should output
[1,2,6,24,120,720]
Added March 10, 2019: See the students' nice solutions
Programs done on Thursday, March 7 2019 class
C13.txt
Contains the following procedures

OptF(f,var): inputs a nice function f (expression)
of a list of variables, and finds the local max and min locations
and values. For example (x^2+y^2+1,[x,y]); should output {[[0,0],1]}.

Grad(f,var): the gradient of the function f of the list of variables var.

GD1(f,var,pt,sz): inputs a function (expression) f in the list of variables var, a point pt
stepsize sz, and a small parameter e indicating when to stop
Performs one step, returns the next point NORMALIZED

GD2(f,var,pt,sz): inputs a function (expression) f in the list of variables var, a point pt
a stepsize sz, and a small parameter e indicating when to stop
Performs one step, returns the next point NOT Normalized

G1(f,var,pt,sz,MaxI,tol): inputs a function f given as an expression, in a list of variables var
a starting point pt, MaxI: number of iterations, and tol a small parameter, we stop when the
norm of the gradient is less than tol, or hit MaxI, iterations. NORMALIZED

G2(f,var,pt,sz,MaxI,tol): inputs a function f given as an expression, in a list of variables var
a starting point pt, MaxI: number of iterations, and tol a small parameter, we stop when the
norm of the gradient is less than tol, or hit MaxI, iterations. NOT NORMALIZED
Homework for March 7, 2019 class (due Sunday March 10, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#13
and an attachment
hw13FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

This is an openended question. In class it was very disappointing that G1 and G2 did not do well.
By starting with very simple functions, like (x1)^2+(y1)^2 of two variables (whose minimum is obviously [1,1]), and then
moving on to more variables and more complicated polynomials, see if either G1 or G2 gets the answer, and what
choices of sz and tol make it work. Perhaps there is a better way to implement this than either G1 or G2.
You can try and read section 7.3 in the Machine learning book in the secret EM19 directory.
Added March 10, 2019: See the students' nice solutions
Programs done on Monday, March 11 2019 class
C14.txt
Contains (in addition to those contained in C12.txt (see above) the following procedures

PtoSeq(P,N): inputs a Precursive sequence in the format [INI,[n,[P0,.., Pk]] where INI is the list of initial values for n=1, ...,k and
P0,..., Pk are polynomials in n, representing the coefficients of the linear recurrence with positive coefficients
P0(n)*x(n)+ ...+ Pk(n)*x(nk)=0 with those initial conditions, and outputs the first N terms of the sequence
(stolen from Victoria Chayes' hw12.txt)

EstAsy(L,n): inputs a long list of pos. numbers L and a variable n, estimates
C,mu,theta, such that L[n] is (approximately! ) asympt. to C*mu^n*n^theta

Asy(rec): inputs a Precursive sequence rec=[INI, [n, [P0,...,Pk]]]
and outputs mu and theta such L[n] is asympototic to C*mu^n*n^theta for some C
Homework for March 11, 2019 class (due Wed. March 13, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#14
and an attachment
hw14FirstNameLastName.txt

By using Asy(rec) as a starting point, write a procedure
BetterAsy(rec,K)
that inputs rec (as in Asy(rec)) and a positive integer K, and outputs the asymptotic expansion to order K of the sequence defined by rec, i.e.
an expression of the form
C*mu^n*n^theta*(1+a1/n+ ... +aK/n^K)
C is a floatingpoint estimate, or, if possible, a conjectured expansion identified by Maple's command
identify(Number)
[For example try:
identify(evalf(Pi));
and you would hopefully get Pi .]
Hint: Once you know mu and theta, set up a template for the sequence as above with unknown symbols a1, ..., aK, plugin the recurrence,
replace 1/n by x, take the Taylor expansion up to the (K+1)th order, set the first (K+1)coefficients to 0
(the first one is already 0), get a system of K equations for the K unknowns, solve them, and plug them back into the template.
Having done that, estimate C, by using PtoSeq(rec,N) for N very large (say 4000) plug into the expression, divide, and get
an approximation to C. Then use that flolatingpoint C to identify it, if possible.
Another hint (added 3/13/2019, 5:00pm): Once you form the tentative expression
Expression:=C*mu^n*n^theta*(1+a1/n+ ... +aK/n^K)
You do not yet replace ny by 1/x. You plugin into the recurrence for the sequence, simplify and normalize, get another expression
(that in some sense should be zero, but of course it is not, since K is finite), but it should be "close" to zero in the sense
that first K+1 taylor coefficients of this new expression should be 0.

By using procedure SeqToP to first find a Precursive description, in order to get rec, and then using
BetterAsy(rec,K), try to find such asympototic expansions, to fifth (or whatever) order for the sum of the rth power of the binomial coefficients
from r=2 to r=6. Also, if possible for other binomial coefficients sums mentioned in hw12.txt
(but I doubt that C will be identified, it would probably be left as a floatingpoint number).
Added March 14, 2019: See the students' nice solutions
Programs done on Thursday, March 14, 2019 class
[Celebrating Pi Day (and Albert E.'s and Victoria C.'s birthdays]
C15.txt

BeterAsy(rec,K,M): inputs a Precursive sequence rec=[INI, [n, [P0,...,Pk]]] pos. integer K and a large pos. integer M
and outputs an asympotic expansion of the sequence fto order K of the form C*mu^n*n^theta*(1+a1/n+...+aK/n^K) for some C and a1, ..., aK

BinToPZ(F,k,n): inputs a product of binomial coefficients F in variables k and n
outputs the Precursive description of a(n):=Sum(F(n,k),k=0..n) , via the Zeilberger algorithm

IsUD(pi): Is pi an updown permutation?

UD(n): the set of updown permutations

ud(n): the number of updown permutations pf length n, done via a nonlinear recurrence

A rational number approximating Pi using updown the number of updown permutations.
It is 2*n*ud(n1)/ud(n).
Homework for March 14, 2019 class (due Sunday, March 24)
Read pp. 117144 of the great book "Machine Learning for Predictive Data Analysis"
by J.D. Kelleher, B. Mac Namee and A. D'Arcy
(available in the secret directory)
Programs done on Monday, March 25, 2019 class
C16.txt
Starting Machinelearning.
Homework for March 25, 2019 class (due Sunday, March 31, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#16
and an attachment
hw16FirstNameLastName.txt

Fix procedure GuessWhoC(x,N) in C16.txt
so that for every x between 0 and 2^k1, GuessWho(x,2^k1) ALWAYS outputs k.

Write a procedure
ABTmod( N,k)
tha has the same input as ABTP but the ith descriptive feature is not whether or not it is divisible by p_{i} but
the remainder when you divide n by p_{i}

A complete binary tree is either a leaf, denoted by the empty list, or a pair [B1,B2] where
B1 and B2 are smaller binary trees. The number of leaves in a binary tree may be defined in the obvious way
(the number of leaves of [] is 1, and the number of leaves of [B1,B2] is the sum of the number of leaves of B1 and the that of B2.

Write a program: BT(n), that inputs a positive integer n and outputs the set of all complete binary trees with n leaves
For example BT(2)={[[],[]]}, BT(3)= {[[][]],[]], [[],[[],[]]]}.

Using the methods of Experimental Mathematics, conjecture a formula for nops(BT(n))

[Challenge] Prove that formula

An ordered tree is either a leaf, denoted by the empty list [], or a list [T1,T2,...Tk] where
T1 and T2, .., Tk, are smaller ordered trees (k is any nonnegative integer). The number of vertices of an ordered tree may be defined in the obvious way
(the number of vertices of [] is 1, and the number of vertices of [T1,T2, ..., Tk] is the sum of the number of vertices of T1,... Tk/

Write a program: OT(n), that inputs a positive integer n and outputs the set of all ordered trees with n vertices
Hint: If an ordered tree has n vertices, then if n >2 then it T=[T1, ..., Tk]. If Tk is an ordered tree with, say, a vertices,
then T'=[T1,..., T(k1)] is an ordered tree with na vertices, and you can use recursion (alias dynamical programming, with option remember)
For example OT(2)={[[]]}.

Using the methods of Experimental Mathematics, conjecture a formula for nops(OT(n))

[Challenge] Prove that formula.
Added March 31, 2019: See the students' nice solutions
Programs done on Thurs., March 28, 2019 class
C17.txt
Decision Trees.

RandDT1(P,d,AF): P=[L,N] inputs the type of the data and an integer d, outputs
a random decision tree of depth <=d, with vertexlabels fromAF

RandDT(P,d): P=[L,N] inputs the type of the data and an integer d, outputs
a random decision tree of depth <=d

Predict(P,T,v): Inputs a profile P
and a decision tree T with that profile and a data vector v
outputs the prediction made by the tree regarding the target value of v

Breakup(P,S,f): inputs a profile of a dataset and a dataset S of vectors of length
nops(P[1]) and a description feature f( between 1 and nops(P[1]) outputs
the list of subsets according to the value of v[f] (there are P[1][f] of them)
[Modified after class]
Homework for March 28, 2019 class (due Sunday, March 31, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#17
and an attachment
hw17FirstNameLastName.txt

Read and understand the new version of Breakup(P,S,f), done after class,
to conform to our notation of ABD (data set) that is a LIST (not a set)
and each entry has the format [NAME,v,TargetValue], where v is the list.

Implement Equation (4.2) in p. 130 of the "Mahine Learning and ..." book. It
inputs a data list (with the above) format and outputs the entropy of that set according
to the target feature. Call this procedure
H(P,S)
[Hint: form a list of length N where the ith component is the number of entries whose target feature is i for each of the
"levels" of the target. Then normalize and use the entropy formula.

Using procedure Breakup implement Equation (4.3) in the same page write a procedure
rem(d,P,S)
where d is one of the nops(P[1]) descriptive feature (i.e. an integer between 1 and nops(P[1]) according to our convention.

Write a procedure
IG(d,P,S)
implementing Eq. (4.4) in p. 131.
Added March 31, 2019: See the students' nice solutions
Programs done on Monday, April 1, 2019 class
C18.txt
Continuing with Decision Trees. In addition to the procedures from C16.txt and C17.txt it contains:

Dodam(N,k): converts ABTP(N,k) to the "canonical format" that we are using where the descriptive and target features are called 1,2,...

H(P,DS): the entropy according to the target feature of the data set DS

IG(P,DS,f): the information gain in picking descriptive feature f as the root of the decision tree

MakeDS(P,DS): implements the ID3 algorithm (to be continued, we just started)
Homework for April 1, 2019 class (due Sunday, April 7, 10:00pm)
[Corrected April 4, 2019, thanks to Victoria Chayes]
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#18
and an attachment
hw18FirstNameLastName.txt

Write a procedure
Gr(d,P,DS)
implementing Eq. (4.8) (section 4.4.1, p. 196 in the .pdf) in the book

Write a procedure
Gini(P,DS)
implementing Eq. (4.9) (section 4.4.1, p. 200 in the .pdf) in the book

Write a procedure, for data sets with CONTINUOUS targets, (now P[2] is no longer a positive integer N but an interval [a,b] indicating that a<=t<=b, t real))
var0(P,DS)
implementing Eq. (4.10) (section 4.4.3, p. 205 in the .pdf) in the book

Write a procedure, for data sets with CONTINUOUS targets, (now P[2] is no longer a positive integer N but an interval [a,b] indicating that a<=t<=b, t real))
BestFeature(P,DS)
implementing Eq. (4.11) (section 4.4.3, p. 205 in the .pdf) in the book
Added April 7, 2019: See the students' nice solutions
Programs done on Thurs., April 4, 2019 class
C19.txt
Finishing decision trees. Contains, in addition to those of previous classes, the following procedures

TBU(P,DS): inputs P and DS, where P=[L,N] is the data "profile", and outputs a list of length
N such that its ith entry is the number of data points with feature i

Majority(P,DS): Inputs P: a profile of our data [L,N] where
L is a list of length k (where k is the number of descriptive features)
and L[i] is the number of different values {1,2, ... L[i]} that
descriptive feature i can assume. Oututs the majority target value

MakeDS1(P,DS,AF,DSprev): implements the ID3 algorithm. The input is P, the data profile [L,N], DS is
the data set and AF is the set of available features, and DSprev is the previous data set.

[completed after class]
MakeDS(P,DS): implements the ID3 algorithm. The input is P, the data profile [L,N], DS is the data set
Homework for April 4, 2019 class (due Sunday, April 7, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#19
and an attachment
hw19FirstNameLastName.txt

By modifying procedure MakeDS(P,DS), write a procedure
MakeDSGr(P,DS)
that does the same as MakeDS(P,DS) but uses the "Information Gain ratio" GR(d,D)
(Eq. (4.8) of the book, from hw18.txt) instead of Information Gain to decide on
the descriptive feature to pick as the root.
Compare the outputs of MakeDS([[2,2,2],2],Dodam(20,3))
and MakeDSGr([[2,2,2],2],Dodam(20,3)).

By modifying procedure MakeDS(P,DS), write procedure
MakeDSGini(P,DS)
that does the same as MakeDS(P,DS) but uses the Gini index
(Eq. (4.9) of the book, from hw18.txt) instead of Information Gain to decide on
the descriptive feature to pick as the root.
Compare the outputs of MakeDS([[2,2,2],2],Dodam(20,3))
and MakeDSGini([[2,2,2],2],Dodam(20,3)).

Write a procedure MakeDSshallow(P,DS,d), that always outputs a decision tree of depth <=d. Once you get
AF to be of size nops(L[1])d it creates a lead with the majority of the remaining data set.

Read sections 7.2 and 7.3 of the KelleherMac NameeD'Arcy book.
Added April 7, 2019: See the students' nice solutions
Programs done on Monday, April 8, 2019 class
C20.txt

BT(n): input a positive integer n returns the set of all binary trees with exactly n leaves
[Code from
Jason Saied's homework 16

NuLeaves(T): the number of leaves in the binary tree T

RandMat(m1,m2,K): a random m1 by m2 matrix with entries from K to K
given as a list of lists

RandMatList(P,K): given a list of positive integers P of length n+1
and a pos. integer K outputs a list of n compatible matrices ready to
be multiplied

EvalBT(L,T): inputs a list L of (compatible( matrices and a binary tree with the number of leaves equal to
the length of L, outputs the matrix product L[1]...L[n] suggested by the tree

PriceM(P,T): inputs a profile of length n+1 and a binary tree with n leaves
outputs the number of multiplications
Homework for April 8, 2019 class (due Sunday, April 14, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#20
and an attachment
hw20FirstNameLastName.txt

Write a procedure
BestTreeDumb(P)
that inputs a profile P (of length n+1) describing the sizes of n matrices to be multiplied by that order, and
outputs the binary tree T that gives the least PriceM(P,T)
Note that you have to examine exponentially many candidates ( the Catalan number).

Write a procedure
BestTreeSmart(P)
that inputs a profile P (of length n+1) describing the sizes of n matrices to be multiplied by that order, and
outputs the binary tree T that gives the least PriceM(P,T) using dynamical programming.
Hint: Use option remember, breakup P into all possible ways, into P1 and P2, use recursion to find the prices given by BestTreeStmart(P1) and
and BestTreeStmart(P2) add to it the price of multiplying the two matrices, and pick the k that gives you the largest score.
Then continue recursively.

By using RandMatList(P,K), with lists P of length, 20, say, and members of P pretty large, and K =300, find for each the best tree, apply
EvalBT(L,T), and see if you can beat Maple.
(First you have to find out how to multiply many matrices in a given order)
Added April 14, 2019: See the students' nice solutions
Programs done on Thurs., April 11, 2019 class
C21.txt
Starting functional chains and networks.
Contains procedures

EvalFC1(L,x,x0): inputs L=[f1,..., fn] expressions in x and a number (or symbol) x0, outputs f1(f2(...fn(x0)))))

RP(d,K,x): a random polynomial of degree d in x with coeff. between K and K

RC(d,K,n,x): a random functional chain of length n

EvalFC(L,x,x0): inputs L=[f1,..., fn] expressions in x and a number (or symbol) x0
outputs [f1(x0),f2(f1(x0)), f3(f2(f1(x0)), ..., fn(....)]:

EvalFCdiff(L,x,x0): inputs a functional chain L, variable x, and number or symbol x0
outputs the derivative of EvalFC(L,x,y) w.r.t. y and y=x0

SumCoeff(A): the sum of the coefficient in a `+` expression .
Homework for April 11, 2019 class (due Sunday, April 14, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#21
and an attachment
hw21FirstNameLastName.txt

[Possibly a challenge, I did not try to do it] Write a procedure
EvalFCdiffk(L,x,x0,k): inputs a functional chain L, variable x, and number or symbol x0
and outputs the kth derivative of EvalFC(L,x,y) w.r.t. y and y=x0.

Find out whether the number of terms of diff(f(g(x)),x$i) and the sum of its coefficients are in the OEIS.

Find out whether the number of terms of diff(f(g(h(x))),x$i) and the sum of its coefficients are in the OEIS.

[Optional Challenge]
[Corrected April 12, 11:30am, thanks to Dr. Z. (the previous version did not make sense)]
This question sets up a neural net with two inputs, n layers with two neurons in each layer, and one output.
For a 2 by 2 matrix A (given as a list of lists) [[a11,a12],[a21,a22]], and a vector of length 2, B=[b1,b2], define
R(A,B)(x,y):=[max(a11*x+a12*y+b1,0), max(a21*x+a22*y+b2,0)] .
Write a procedure
EvalNR2(L,c1, c2, x0,y0)
That inputs a list L of pairs
[A1,B1],[A2,B2], ..., [An,Bn]
and ouputs the value in going from left to right and applying to the current vector the
transformation
[x,y] > [max(a11*x+a12*y+b1,0), max(a21*x+a22*y+b2,0)] .
for the current A=[[a11,a12],[a21,a22]], and B=[b1,b2],
max(c1*x+c2*y,0) to the final [x,y].
Use plots[plot3d] to plot a few such functions.
Added April 14, 2019: See the students' nice solutions
Programs done on Monday, April 15, 2019 class
C22.txt
Trying to teach the machine how to teach us to play Peg Solitaire.
Contains procedures:

PSB(m,n): The board of Peg Solitaire with a central area that is a square of side 2n1, where on each of the four sides are
attached an m by n rectangle. The standard board is PSB(2,2).

IP(m,n): the initial position, where the central cell, [m+n,m+n], is removed.

RHM(S,B): Given a position S in a pegsolitaire with board B, all the right horizontal moves in Peg Solitaire from position S

LHM(S,B): Given a position S in a pegsolitaire with board B, all the left horizontal moves in Peg Solitaire from position S

UVM(S,B): Given a position S in a pegsolitaire with board B, all the UpVertical moves in Peg Solitaire from position S

DVM(S,B): Given a position S in a pegsolitaire with board B, all the down vertical moves in Peg Solitaire from position S

Moves(S,B): The set of all possible legal moves from position S in a Peg Solitaire with board B

RG(S,B): a random game starting at position S

Cont(L,B) : inputs a partial history of a PegSolitaire game, outputs the set of all possible extensions by one move

AllGamesK(S,B,K): all partial games of length K,

PlotPos(S): plots position S

EF1(S,B): the number of moves available at position S with Peg Solitaire with board B, the most naive
evaluation function (that turned out to be disappointing)

SmartOne(S,B,f): the best move from S using evaluation function f (that inputs S and B)

SmartGame(S,B,f): A "smart" game guided by evaluation function f

BestRand(S,B,K): the best of K random game starting at position S and with board B

Homework for April 15, 2019 class (due Sunday, April 21, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#22
and an attachment
hw22FirstNameLastName.txt

In my code a move was really the position resulting from the move. Using the data structure
[[a,b],[1,0]]
to indicate moving the peg in position [a,b] over the peg in position [a+1,b], assuming that [a+2,b] is in the board and is currently empty,
with analogous meanings for [[a,b],[1,0]], [[a,b],[0,1]], [[a,b],[0,1]], write a procedure
NiceMoves(S,B): The set of all possible legal moves from position S in a Peg Solitaire with board B
that uses this more compact description.

To interface it with the previous convention, write a procedure
ExecuteMove(m,S,B)
that inputs m=[[a,b],[1,0]] or m=[[a,b],[1,0]] etc. and outputs the set of remaining pegs.

Write
NiceBestRand(S,B,K)
that uses the new convention to get the sequence of moves in a game.

Write a procedure
Verbose(S,B,L)
that inputs S, B, and L, the output of NiceBestRand(S,B,K) (or another procedure like it)
and outputs a set of instructions clear to a sevenyear old. Like
Move the peg in location [4,5] over the peg in location [4,6], thereby making locations [4,5] and [4,6] empty, and location [4,7] occupied
[Hint: first write a procedure
Verbose1(S,B,m)
that does it for an individual move.

Experiment with rectangular m by n boards with the bottomleft peg removed, and see whether you can get good solutions

[Lottery, 5 dollars to the best solution] Run
BestRand(IP(2,2),PSB(2,2),10^5)
all night, and see what you can come up with. The lucky winners will share the prize

[Big Challenge, 20 dollars, I don't know the answer]
Find an evaluation function,f , for which
SmartGame(IP(2,2),PSB(2,2),f)
gives you a solution with one peg left, if possible at the central location.

[Added April 16, 2019]
After class, I added procedures RectBoard(m,n) and RectBoardIP(m,n), for the board of a Peg Solitaire with an
m by n board rectangular ,
and its initial position with the leftmostbottom peg ([1,1]) removed.
Before class, I also wrote procedure
AllGames(S,B,K)
that gives the set of ALL the start of games up to length K.
In particular
AllGames(S,B,nops(S)1)
outputs the set of ALL solutions (possibly an empty set). Alas for the actual Peg Solitaire with the size of S being 32, it is impractical.

How many solutions of Peg Solitaire with a 3 by 4 rectangular board are there?
For how many of them is the last peg at the position of the initial hole, [1,1]?

How many solutions of Peg Solitaire with a 3 by 5 are there? If there are no solutions with only one peg left, what is the best that can be done?

[Optional Challenge, 10 dollars] By looking at a computergenerated solution of a 3 by 4 board, devise an algorithm that does it
for a 3 by n board for any even n.

[Optional Challenge, 10 dollars] By looking at a computergenerated solution of a 3 by 4 board, and possibly a 3 by 6 board,
try to devise a strategy (without peeking at the internet) that does the usual Peg Solitaire.

[Optional Human Challenge, 10 dollars] Prove that the best that one can do for a 3 by n board, with n, odd, is to have
two pegs remaining.
[Added April 25, 2019]: Victoria Chayes solved this (and possibly other problems). She won ten dollars, and
See
Victoria Chayes' Maple source code and
.pdf
Added April 22, 2019: See the students' nice solutions
Programs done on Thurs., April 18, 2019 class
C23.txt
Getting ready for "back propagation" using the chain rule.
Homework for April 18, 2019 class (due Sunday, April 21, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#23
and an attachment
hw23FirstNameLastName.txt

Maple can easily compute the millionthFibonacci number mod 2003, say using the program
F(n,K)
we did in class, by typing
F(10^6,2003);
But F(n,K) is not as clever as I claimed. It can't find the 10^20th Fibonacci number mod 2003.
Write a program that finds F(n,K) for very large n.
Hint: using Victoria's suggestion, we "pack" F(n),F(n1) into a vector of length 2
write
A(n):=[F(n),F(n1)]. Then, we have
A(n)=[F(n),F(n1)]^T=[F(n1)+F(n2),F(n1)]^T=matrix([[1,1],[1,0]])A(n1)
Calling the 2 by 2 matrix matrix([[1,1],[1,0]]), B
We have
A(n)=B^n [1,0]^T
Now use the "repeated squaring trick" mod K, to write a program
Fc(n,K)
that does what the "clever" F(n,K) does, but much faster, and for much larger n.

Write a program
Tc(n,K)
that finds the nth Tribonacci number mod K. What is
Tc(10^100,2003);?
Added April 22, 2019: See the students' nice solutions
Programs done on Monday, April 22, 2019 class
C24.txt
Starting General "neural nets" with arbitrary transformations.
Contains procedure

RMP(x,d,K): a random poly in the list of
variables x of degree d with coefficients from 1 to K do

RT(x,d,K,n1,n2): inputs a LETTER x, integers d and K and pos. integers n1, n2
outputs a RANDOM POLYNOMIAL TRANSFORMATION from R^n1 to R^n2 of degree d
using the variables x[1], .., x[n1]

RMC(x,d,K,L): a random chain of poly transformations of length n of
of degree k with coefficients from 1 to K starting at L[1]dim space
and ending at L[n+1] dimensional space

EvalMC(L,x,x0): inputs a vector x0 and a chain of transformations L and
a letter x (indicating that our variables are x[1],x[2], ...)
outputs the output of the chain

Jac(T,x,n1),inputs a transformation T from R^n1 to R^nops(T) outputs
the Jacobian the n1 by nops(T) matrix (symbolically) in terms of x[1], ...
Homework for April 22, 2019 class (due Sunday, April 28, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#24
and an attachment
hw24FirstNameLastName.txt

An elementary transofrmation in ndim space is a mapping that maps x[i] to a*x[i]+ b*x[j]^r for some constant r and positive integer r,
and leaves all the other variables the same. For example
[x1,x2,x3] > [x1, 3*x2+5*x3^6, x3]
Convince youself that the Jacobian determinant of an elementary transformation is identically constant

Convince yourself that the inverse of an elementary transformation is also an elementary transformation, what is it?

[Updated April 23, 2019, thanks to Lauren Squillace]
Write a procedure
RandCompElemTrans(x,n,N,K1,K2,R1)
That inputs a letter x, a positive integer n (for the dimension) a positive integer N, and pos. integers K1 and K2 and
outputs a complicated polynomial transformation that is the composition of N random elementary transformation
x[i]> a*x[i]+ b*x[j]^r
For a,b between 1 and K1 and K2 between 1 and K2, and r is an integer from 1 to R1.
It should also output its inverse transformation, thereby generating
many pairs of polynomial transformations [T1,T2] that are inverses of each other and whose Jacobian are identically (nonzero!) constants.

[Optional challenge, $1000]: Prove that if a polynomial transformation in dimension >=2 has a nonzero constant Jacobian determinant,
then its inverse transformation (that exists by a general theorem) is also a polynomial transformation.
Added April 28, 2019: See the students' nice solutions
Programs done on Thurs., April 25, 2019 class
C25.txt
Implementing a neural network with on one hidden layer.

sig(u) : the famous Sigmoid function, u>1/(1+exp(u)):

NN2(x,W,Wp): a Maple implementation of Fig. 6 in
the amazing article of Xin Rong
It inputs a numerical column vector (data of descriptive features) of length K say,
a matrix W of size by N, say, and a matrix Wp of size N by M, say.
Outputs the numerical vector of size M , y, computed by this "deep" neural net.

Loss1(x,t,W,Wp): inputs vectors x and t (t=actual target, "gold standard")
and outputs the loss using the neural net (W,Wp)

Loss(S,W,Wp): the total loss of the data set S

QD(y,t): Eq. (78) of the above paper Ej'

BPG1(x,t,W,Wp,eta): [Just started, to be continued in homework].
Inputs x and t, W and Wp, and the learning rate, eta, outputs the updated
matrices W and Wp using Equations (81) and (85) on pages 19 and 20 of
Xin Rong's paper
Homework for April 25, 2019 class (due Sunday, April 28, 10:00pm)
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#25
and an attachment
hw25FirstNameLastName.txt

Finish procedure BPG1(x,t,W,Wp,eta) (note the added parameter, eta, for the learning rate), and fully implement pp. 1920 in
Xin Rong's paper.
In other words Eq. (80) and (85) (that depend on other equations).

Read and understand all of Xin Rong's fascinating paper.

As preparation for the
Final Class project
Collect the data for the set of people that Yukun Yao will assign you, so that we can
use it in next week's class to illustrate some basic concepts and techniques in statistics that are
important in machine learning.
Added April 28, 2019: See the students' nice solutions
Programs done on Mon., April 29, 2019 class
C26.txt
The very beginning of "computational linguistics". Contains procedures:

FT(VOC,A): inputs a vocabulary list VOC (a list of lists) and an alphabet A
( a list of letters) and outputs the frequenncy table of ALL letters that show up

ENT(L): the entropy of the prob. dist. L

TRM(VOC,A,I1,J1): inputs a vocabulary set VOC, an alphabet A, and pos. integers I1, J1
outuputs the nops(A) by nops(A) matrix whose i,j entry is conditional probabity
Letter[J1]=jLetter[I1]=i

MakeWS(VOC1,VOC2): creates a random K1 by K2 matrix each of whose rows
belongs to VOC1 and each of whose columns belongs to VOC2
[To be continued as homework]
[Optional] Homework for April 29, 2019 class (due Sunday, May 5, 10:00pm)
Update May 2, 2019: Since the project is due May 14, 2019, the homework 26 is optional. You
should work on your chosen group project.
Please email ShaloshBEkhad at gmail dot com an email with
Subject: hw#26
and an attachment
hw26FirstNameLastName.txt

Write procedure
MakeWS(VOC1,VOC2)
that inputs two vocabularies (each with the same number of words) and outputs a random "word rectangle" where all the rows belong to VOC1
and all the words belong to VOC2. (Of course, VOC1 and VOC2 can be the same, and then you get a "word square"
Definition: A word rectangle with respect to the list of words VOC1 VOC2 is a matrix each of whose rows
belongs to VOC1 and each of whose columns belongs to VOC2. For example if {math,amoi} is a subset of VOC1
and if { ma,am,to,hi} is a subset of VOC2, then the following is a 2 by 4 word rectangle.
math
amoi
[Note: To get data use
EV3.txt ,
EV4.txt ,
EV5.txt ,
EV6.txt ,
EV7.txt ,
EV8.txt
]
Hint: You many need to be clever, and first write a prodedure TRUNC(VOC,K) that inputs a vocabulary and outputs
the set of prefixes of length K.

Write procedure
MakeSWS(VOC1)
that inputs a vocabulary, VOC1 and outputs a random "word square" that is a SYMMETRIC word matrix, where each row is the same as the corresponding column.
For example: [[d,a,d],[a,r,e],[d,e,n]]

If computationally feasible (I know that it is for the 3 by 3 case), write a procedure
MakeAllSWS(VOC1)
That outputs the set of ALL such symmetric word squares.

Unless you moved to the "Make a WordRectangles Puzzle Webbook" that Yonah BiersAriel kindly agreed to coordinate (continuing we today's homework),
start to work on the assignment that Yukun Yao asked you to do for the class project. People who moved to Yonah's project
(up to three people, first come first served, wait for my approval) should wait for instructions from Yonah.
Added May 2, 2019: Here are the VERY PRELIMINARY Maple packages for the two projects

Project 1 [Data Analytics, illustrated with Rutgers Math Faculy but applicable in general],
coordinated by Yukun Yao.

Project 2 [Creating Pure Word Squares and Rectanles and possibly other word puzzles],
coordinated by Yonah BiersAriel.
Stuff discussed on Thurs., May 2, 2019 class
We discussed the two projects and explored the two very preliminary drafts of the Maple packages
Project 1 (Yukun Yao's group) and
Project 2 (Yonah BiersAriel's gropu),
and how to make it better. The homework for today is to start working on the group project, due May 14, 2019.
Added May 14, 2019: Enjoy the perfect, noblacksquare computergenerated puzzlebook
computergenerated puzzlebook
that forms Project 2. Performed by Yonah BiersAriel (chair),
Matthew Hohertz, and Jinze Li, Lauren Squllace.
Added May 15, 2019: Enjoy the
"Metamathematical" analysis of Rutgers math faculty
accomplishment vs. their salaries that forms Project 1. Performed by Yukun Yao (chair),
Victoria Chayes, Tong Cheng, Terence Coelho, Quentin Dubroff, Dodam Ih, Joe Olsen, Jason Saied and Tianhao Zhang.
Added May 22, 2019: Read the students' evaluations
Dr. Z.'s teaching page