Last Update: May 22, 2019.

• Teacher: Dr. Doron ZEILBERGER ("Dr. Z")

• Classroom: Allison Road Classroom Building [Busch Campus], IML Room 116.
  

• Time: Mondays and Thursdays , period 3 (12:00noon-1:20pm)

• Main Textbook: The Concrete Tetrahedron by Manuel Kauers and Peter Paule
  

• Dr. Zeilberger's Office: Hill Center 704
• Dr. Zeilberger's Email: DoronZeil at gmail dot com
  
• Dr. Zeilberger's Office Hours (Spring 2019): MTh 9:05-10:05am

Additional Texts

• Section 3.7 of Leslie Valiant's masterpiece. [Buy the book!]

• Xin Rong's excellent article word2vec Parameter Learning Explained.

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 computer-algebra 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 experimental-symbolic mathematics using the excellent book `The Concrete Tetrahedron' by Manuel Kauers and Peter Paule. An E-book 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

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

• OurMin(L): inputs a list L of numbers and outputs a minimal element and its location.

• SelS(L): Inputs a list L and outputs the sorted list, using the very inefficient (quadratic) Selection sort.

Homework for Thurs., Jan. 24, 2019, class (due Sunday Jan. 27, 10:00pm)

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.

1. [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 .

2. [For everyone]. Read and understand pp. 1-12, of the Kauers-Paule "Concrete Tetrahedron" (in the secret url I told you about. If you forgot, Email me).

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

4. [Mandatory for experts, optional for novices] Write a program c(n) that inputs a non-negative 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.

5. [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

• 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)

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.

1. [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. 30-61 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw2YourName.txt .

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

3. [For everyone] (human exercises) Solve problems 1.1-1.5 at the end of chapter 1 of the book (pp. 15-16)
   [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]

4. [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 plug-in t=1 and get a recurrence for the second moment , m₂(n) of that random variable, and then use the famous result that the variance is m₂(n)-c(n)²].

Added Feb. 4, 2019: See the students' nice solutions  

Programs done on Thurs., Jan. 31,, 2019

• 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.

1. [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. 62-92 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw3YourName.txt .

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

3. [For experts, but novices are strongly encouraged] The scaled k-th moments of a probability distribution is m_k/ (m₂)^(k/2), where m_k is the k-th 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.

4. 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?

5. 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.

6. [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

• 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 non-neg. integers n and k and outputs the SET of compositions of n into k parts (vectors of non-neg. integers that add-up 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.

1. [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 .

2. [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)).

3. 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?

4. [Human exercise] Can you prove your guess?

5. [Human and/or machine exercise] Can you conjecture a closed-form 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

contains all the procedures of C4.txt (listed in Help4(); ) as well as the following new procedures

• PreMag(a,b,n):inputs non-neg. integers n,a,b, and outputs the set of a by b matrices (given as lists of lists) with non-negative entries and row sums n,

• IsMagic(A,k): inputs a matrix A and outputs true iff all the columns of A add-up to k

• MagRec(a,b,n): the set of a by b matrices with non-neg. 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.

1. Read and understand sections 2.1, 2.2, and 2.3 (pp. 17-28)

2. [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 one-line procedure
   M2(k,n)
   that inputs k and n and outputs this number.

3. 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

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 add-up 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.

1. [Corrected, thanks to Songhao Zhu] A quasi-polynomial 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 quasi-polynomial 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 quasi-polynomial of period m. You can use GuessPol as a subprocedure.It should return FAIL if it fails.

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

3. 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]

4. 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/((1-q)(1-q^2) ... (1-q^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"

5. Conjecture quasi-polynomial 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

• Comp(n,k): inputs non-neg. integers n and k and outputs the SET of compositions of n into k parts (vectors of non-neg. integers that add-up 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.

1. Either using Maple's combinat[fibonacci], or making up your own home-made 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

2. Read and understand pp. 3-6 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

Contains the following new procedures:

• CtoSeq(C,N): inputs a C-finite 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 C-finite sequence C=[INI,Rec] (denoting a sequence of order k, say) k=nops(INI) and a(n)=Rec[1]*a[n-1]+ ... + Rec[k]*a[n-k] . Fib is [[0,1],[1,1]] and outputs a polynomial P, in x[1], ..., x[r], such that P(a(i),...,a(i+r-1))==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.

1. Write a program A(n) that inputs a non-negative 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).

2. 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]

3. Write a program SeqToC(L) that inputs a sequence L and tries to guess a C-finite 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.]

4. Using both CtoSeq and your SeqToC, write a C-finite "calculator", i.e. procedures

   AddC(C1,C2) and MulC(C1,C2)

   that inputs pairs of C-finite sequences C1, C2, and outputs the C-finite description of their sum and product.

5. [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(n-1)+ca(n-2)

   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

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 cut-off c that >=c gets 1 (admitted) and 0 (rejected)

• TestP(L,c): Inputs a data set of pairs [height,1 or 0] and a cut-off 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 cut-off c that >=c gets 1 (admitted) and 0 (rejected) and a prob. p of mis-classifying 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.

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

2. Generalize ArData(L1,H1,N,c) to an arbitary number of dimensions. Write a procedure but with random points from the n-dimensional 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.

3. 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.

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

5. 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

Contains the following procedures

• [From C8.txt] Ctoeq(C,N): inputs a C-finite 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 C-finite 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 C-finite description. If it fails, it returns FAIL. [from Victoria Chayes' homework, hw8.txt]

• CtoRat(C,x): inputs a C-finite 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.

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

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

3. Using GuessAlg(L,F,x), guess algebraic equations for the sequences

   [seq(binomial(m*k,k)/((m-1)*k+1),k=0..60)]

   For m=2,m=3, m=4, m=5, m=6, m=7   .

   Can you guess a meta-pattern, in terms of m?

4. [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

5. 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 blow-up at the origin) and returns the first N+1 terms (starting at n=0) of the coefficient of xⁿ yⁿ. For example

   DiagToSeq(1/(1-x-y),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.]

6. 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/(1-x-y), 1/(1-x-y+2*x*y), 1/(1-x^2-y^2+x*y), 1/(1-x-2*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

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 F-INI(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.

1. Let an algebraic sequence be coded by the 4-tuple [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].

2. 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

Contains the following procedures

• SeqToP1(L,n,k,d): Inputs a list of length >= (k+1)*(d+1)+k+4, outputs a P-recursive representation (if it exists) that fits the list. For example, try:SeqToP1([seq(i!,i=1..20)],n,1,1);

• SeqToP(L,n,MaxC): Inputs a list outputs a P-recursive representation (if it exists), and maximum complexity that fits the list. The output is the lowest Degree+Order that fits it, and we prefer lower order. For example, try:

  SeqToP([seq(i!,i=1..20)],n,2);

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.

1. Read and understand the Maple code contained in C12.txt

2. 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]

3. The famous Zeilberger's algorithm promises that for any product of binomial coefficients, that contain binomial(n,k) in it the sequence is P-recursive. 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 (P-recursive 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) ?

4. Write a procedure

   PtoSeq(P,N)

   that inputs a P-recursive 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

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 step-size 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 step-size 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.

1. This is an open-ended question. In class it was very disappointing that G1 and G2 did not do well. By starting with very simple functions, like (x-1)^2+(y-1)^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

Contains (in addition to those contained in C12.txt (see above) the following procedures

• PtoSeq(P,N): inputs a P-recursive 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(n-k)=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 P-recursive 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

1. 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 floating-point 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, plug-in 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 flolating-point 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 plug-in 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.

   ---

2. By using procedure SeqToP to first find a P-recursive 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 r-th 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 floating-point number).

Added March 14, 2019: See the students' nice solutions  

Programs done on Thursday, March 14, 2019 class

• BeterAsy(rec,K,M): inputs a P-recursive 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 P-recursive description of a(n):=Sum(F(n,k),k=0..n) , via the Zeilberger algorithm

• IsUD(pi): Is pi an up-down permutation?

• UD(n): the set of up-down permutations

• ud(n): the number of up-down permutations pf length n, done via a non-linear recurrence

• A rational number approximating Pi using up-down the number of up-down permutations. It is 2*n*ud(n-1)/ud(n).

Homework for March 14, 2019 class (due Sunday, March 24)

Read pp. 117-144 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

Starting Machine-learning.

• GuessWhoS:(x,N): simulating a stupid guess who game with a number from 0 to N

• ManyGHS(N,K,t): The average and standard deviation of K runs o fHuessWhoS(x,N)

• GuessWhoC(x,N):Simulating a clever guess who game with a number from 0 to N (needs fixing, see homework problem 1)

• SEent(P): The (Shannon) amount of information in bits of the discerte prob. distribution P

• Profile(n,k): inputs a positive integers n and k outputs a list of 0,1 of length k whose i-th item is "Is n divisible by prime[i]" for i from 1 to k (0=false, 1=true)

  For example Profile(10,3) should output [1,0,1].

• ABTP(N,k): Inputs a positive integer N and pos. integer k outputs an ABT for the data generated from them using the k descriptive features `is n divisible by the k-th prime?'

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

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

2. Write a procedure

   ABTmod( N,k)

   tha has the same input as ABTP but the i-th descriptive feature is not whether or not it is divisible by p_i but the remainder when you divide n by p_i

3. 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.
   1. 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)= {[[][]],[]], [[],[[],[]]]}.
   2. Using the methods of Experimental Mathematics, conjecture a formula for nops(BT(n))
   3. [Challenge] Prove that formula

4. 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 non-negative 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/
   1. 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(k-1)] is an ordered tree with n-a vertices, and you can use recursion (alias dynamical programming, with option remember)

      For example OT(2)={[[]]}.

   2. Using the methods of Experimental Mathematics, conjecture a formula for nops(OT(n))
   3. [Challenge] Prove that formula.

Added March 31, 2019: See the students' nice solutions  

Programs done on Thurs., March 28, 2019 class

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 vertex-labels 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 data-set and a data-set 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

1. 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.

2. 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 i-th 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.

3. 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.

4. Write a procedure
   IG(d,P,S)
   implementing Eq. (4.4) in p. 131.

Programs done on Monday, April 1, 2019 class

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

1. Write a procedure

   Gr(d,P,DS)

   implementing Eq. (4.8) (section 4.4.1, p. 196 in the .pdf) in the book

2. Write a procedure

   Gini(P,DS)

   implementing Eq. (4.9) (section 4.4.1, p. 200 in the .pdf) in the book

3. 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

4. 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

Programs done on Thurs., April 4, 2019 class

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 i-th 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

1. 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)).

2. 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)).

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.

4. Read sections 7.2 and 7.3 of the Kelleher-Mac Namee-D'Arcy book.

Programs done on Monday, April 8, 2019 class

• 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

1. 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).

2. 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, break-up 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.

3. 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)

Programs done on Thurs., April 11, 2019 class

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

1. [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 k-th derivative of EvalFC(L,x,y) w.r.t. y and y=x0.

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

3. 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.

4. [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.

Programs done on Monday, April 15, 2019 class

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 2n-1, 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 peg-solitaire with board B, all the right horizontal moves in Peg Solitaire from position S

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

• UVM(S,B): Given a position S in a peg-solitaire with board B, all the Up-Vertical moves in Peg Solitaire from position S

• DVM(S,B): Given a position S in a peg-solitaire 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 Peg-Solitaire 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

1. 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.

2. 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.

3. Write

   NiceBestRand(S,B,K)

   that uses the new convention to get the sequence of moves in a game.

4. 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 seven-year 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.

5. Experiment with rectangular m by n boards with the bottom-left peg removed, and see whether you can get good solutions

6. [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

7. [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.

8. [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 leftmost-bottom 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 computer-generated 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 computer-generated 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

Programs done on Thurs., April 18, 2019 class

Getting ready for "back propagation" using the chain rule.

• Box(n): the set of 0-1 vectors of length n

• IsGG(v): Does v contain 11

• Fsss(n):the n-th Fibonacci number using the extremely stupid way (using one of the Combinatorial definition of fibonacci number, the number of 0-1 vectors of length n avoiding 11

• Fss(n): the n-th Fibonacci number using the very stupid way

• Fs(n): the n-th Fibonacci number using the usual way mod K

• F(n,K): the n-th Fibonacci number the clever way mod K

• RP(x,d,K): a random poly in x of degree k with coefficients from 1 to K do

• RC(x,d,K,n): a random chain of length n of poly in x of degree k with coefficients from 1 to K do

• EvalC(L,x,x0): inputs a listL of expressions in the variable x and a number x0 outputs L[n](L[n-1](.... L[1](x0)))))))))
  [Modified after class]

• EvalCD(L,x,x0): inputs a listL of expressions in the variable x and a number x0 outputs L[n](L[n-1](.... L[1](x0))))))))) followed by the derivative of the composition
  [Modified after class]

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

1. Maple can easily compute the millionth-Fibonacci 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^20-th 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(n-1) into a vector of length 2 write
   A(n):=[F(n),F(n-1)]. Then, we have

   A(n)=[F(n),F(n-1)]^T=[F(n-1)+F(n-2),F(n-1)]^T=matrix([[1,1],[1,0]])A(n-1)

   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.

2. Write a program

   Tc(n,K)

   that finds the n-th Tribonacci number mod K. What is

   Tc(10^100,2003);?

Programs done on Monday, April 22, 2019 class

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

1. An elementary transofrmation in n-dim 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

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

3. [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 (non-zero!) constants.

4. [Optional challenge, $1000]: Prove that if a polynomial transformation in dimension >=2 has a non-zero constant Jacobian determinant, then its inverse transformation (that exists by a general theorem) is also a polynomial transformation.

Programs done on Thurs., April 25, 2019 class

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

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

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

3. 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.

Programs done on Mon., April 29, 2019 class

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]=j|Letter[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

1. 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.

2. 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]]

3. 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.

4. Unless you moved to the "Make a Word-Rectangles Puzzle Web-book" that Yonah Biers-Ariel 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 Biers-Ariel.

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)
[Here is the DATA set for Rutgers, and here is a much bigger data set with 10 departments]
and Project 2 (Yonah Biers-Ariel'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, no-black-square computer-generated puzzle-book computer-generated puzzle-book that forms Project 2. Performed by Yonah Biers-Ariel (chair), Matthew Hohertz, and Jinze Li, Lauren Squllace.

Added May 15, 2019: Enjoy the "Meta-mathematical" 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