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

Teach yourself the basics of Maple by reading Frank Garvan's golden-oldie 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


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.

  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

C2.txt , Contains procedures [In addition to those of C1.txt whose Help is now "Help1();" ):

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.

  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 Hn 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 , m2(n) of that random variable, and then use the famous result that the variance is m2(n)-c(n)2].

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


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

C3.txt , Contains procedure

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 mk/ (m2)(k/2), where mk 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

C4.txt ,

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

C5.txt

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

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

C6.txt

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

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

C7.txt

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( Fn, Fn+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

C8.txt

Contains the following new procedures:

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

C9.txt

Contains the following new procedures:

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

C10.txt

Contains the following procedures

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 xn yn. 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

C11.txt

Contains the following procedures

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

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.

  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

C13.txt

Contains the following procedures

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

C14.txt

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

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


[Celebrating Pi Day (and Albert E.'s and Victoria C.'s birthdays]
C15.txt

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


C16.txt

Starting Machine-learning.

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 pi but the remainder when you divide n by pi

  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


C17.txt

Decision Trees.

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.

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:

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


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

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.

Added April 7, 2019: See the students' nice solutions  


Programs done on Monday, April 8, 2019 class


C20.txt

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)


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

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.


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:

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.


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

  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);?


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

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.

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.

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.

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:

[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

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