Math 640: EXPERIMENTAL MATHEMATICS
Spring 2011 (Rutgers University) Webpage
http://www.math.rutgers.edu/~zeilberg/math640_11.html
Last Update: May 16, 2011.
 Teacher:
Dr. Doron ZEILBERGER ("Dr. Z")

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

Time: Mondays and Thursdays , period 3 (12:00noon1:20pm)

"Textbooks": classical articles,

Dr. Zeilberger's Office: Hill Center 704 (732 445 2390 Ext. 1326)

Dr. Zeilberger's Email:
zeilberg at math dot rutgers dot edu (you MUST have MathIsFun in the message,
or ExpMathRocks)

Dr. Zeilberger's Office Hours: MTh 10:30am11:30am and by appointment
Description
Experimental Mathematics used to be considered an oxymoron,
but the future of mathematics is in that direction.
In addition to learning the
philosophy and methodology of this budding field, students will
become computeralgebra wizards, and that should be very helpful in whatever
mathematical specialty they are doing (or will do) research in.
We will first learn Maple, and how to program in it.
This semester we will focus on ALGORITHMS, both
general (complexity theory, trying to prove that P ≠ NP or at least
get closer to it than people did before), but first learning what
is a computation and what is a Turing Machine and other computational
models (simulating them all in Maple).
This would be one part.
The other part will focus on a very specific kind of algorithms,
sorting algorithms, in particular those useful in bioinformatics
(and for sorting pancakes by flipping).
But the actual content is not that important,
it is mastering the methodology of computergenerated and
computerassisted research that is so crucial for your future.
There are no prerequisites, and no previous programming knowledge is assumed.
Also, very little overlap with previous years.
The final projects for this class may lead to journal publications.
Volunteer tutors
The following Maple whizes volunteered to help
novices with any questions about Maple
 Andrew Baxter: baxter at math
 Edi(nah) Gnang: kgnang at gmail dot com
 Emilie Hogan: eahogan at math
 Dennis Hou: dhou at eden
 Brian Nakamura: bnaka at math

David J. Wilson: davidjwi at math
Added March 27, 2011:
PICK (OR SUGGEST!) A PROJECT
Diary and Homework
Programs done on Thurs., Jan. 20, 2011

Jan20.txt ,
Contains procedures

MK(n):
inputs an integer n and evaluates the expression
in Amer. Math. Monthly problem 11545 (Jan. 2011)
proposed by Manuel Kaures and ShengLan Ko.

MA(m):
inputs an integer m and evaluates the expression
on the left side of Amer. Math. Monthly problem 11544 (Jan. 2011)
proposed by Max A. Alekseyev .
Homework for Thurs., Jan. 20, class (due Jan. 24, 2011)
All homework should be handedin on paper at the beginning of the
next class.

(For Novices only)
Read and do all the examples, plus make up similar ones,
in the first 30 pages of Frank Garvan's awesome Maple booklet.
[Hand in a printout of two pages with sample commands]

Find (experimentally!) the answer to Amer. Math. Monthly problem 11546,
proposed by Kieren MacMillan and Jonathan Sondow.
If you feel like it, try and prove it rigorously.

Write a program that inputs an "explicit"
(i.e. one given by an expression) C^{2} function
and outputs the difference between the right side and
left side of AMM Problem 11548 (proposed by Cezar and Tudorel Lupu)
try it out for many functions and verify the claim empirically.
If you feel like it, also prove it.

(For experts only)
Write a program that inputs a positive integer d and outputs
all polynomials of degree ≤ d in x that satisfy
the condition of AMM problem 11549.
f(f(f(x)))3f(x)+2x=0 .
(i.e. replace "continuous"
by polynomials of degree ≤ d .)
 (For everyone). Read and understand the
wikipedia entry on
Boolean Logic
Programs done on Monday, Jan. 24, 2011
Jan24.txt ,
Contains procedures

F(i,x,y): inputs an integer i, 1<=i<=10 and
logical constants (i.e. true or false) and
outputs the value of the #iGENUINE 2variable
Boolean function

An example of a straightline program
with four input gates and three additional gates (alias instructions),
namely:
SL1:=[1,2,3,4,[5,1,2],[6,3,4],[10,5,6]];

EvalB(n,SLP,L1): Inputs a pos. integer n
a "straight line program" SLP and a list
L1 of length n of true and false's (t and f)
outputs the values of the function computed
by this SLP for each of the gates

nCube(n): The set of all nvectors of t's and f's
Homework for Monday, Jan. 24, class (due Jan. 27, 2011)
All homework should be handedin on paper at the beginning of the
next class.

(For novices only)
Read and do all the examples, plus make up similar ones,
in the first 60 pages of Frank Garvan's awesome Maple booklet.
[Hand in a printout of two pages with sample commands]

(For novices only) The current procedure nCube(n) outputs the
set of vertices of the ndimensional cube,
{t,f}^n.
Write a more general program nCubeG(n,S) that inputs
a twoelement set S and outputs the set
(with 2^{n} elements) of all vectors of
length n (expressed as lists),
whose components are elements of S. Make sure that nCubeG(n,{t,f});
gives the same output as nCube(n);

(For experts, optional challenge for novices)
Write a more general program nCubeG(n,S) that inputs
any set S and outputs the set (with S^{n} elements)
of all vectors of length n (expressed as lists),
whose components are elements of S. Make sure that nCubeG(n,{t,f});
gives the same output as nCube(n);

(For experts, optional challenge for novices)
Write a program BF(n,SLP) that inputs a positive integer n and
a straightline program SLP (in the format that we are using,
[1, ...., n, [Inst1, Inst2, ..., Instk]], where Inst1, Inst2
are "instructions" written as triplets, and outputs the
"Boolean function" that it evaluates expressed as subset of
nCube(n). (Recall that there is an obvious onetoone correspondence
between Boolean functions on n variables and subsets of the ndimensional
discrete unit cube:
f> {v; v in nCube(n), f(v)=true} ).
Programs done on Thursday Jan. 27, 2011
Jan27.txt ,
Contains the procedures of Jan24.txt as well as the following new procedures:

BF(n,SLP): inputs a straightline program SLP of
n input variables and outputs the Boolean function
(as a set of vectors that yield true) that it computes

VtoS(i,n): inputs positive integers i and n
1<=i<=n and outputs the Boolean function
expressed as a set of nvectors of {t,f}'s
corresponding to x[i]

BFn(n,SLP): another way to do BF(n,SLP) by computing the "function"
of each instructions

RandSLP(n,K): inputs positive integers n and K and outputs a random straight line program
with n input gates and K other gates.
Homework for Thurs., Jan. 27, class (due Jan. 31, 2011)
All homework should be handedin on paper at the beginning of the
next class.
Note: I thank David Wilson for pointing out errors in the previous version
(when I said "conjunctive normal form" I meant "disjunctive normal form")

(For novices only)
Read and do all the examples, plus make up similar ones,
in pages 6090 of Frank Garvan's awesome Maple booklet.
[Hand in a printout of two pages with sample commands]

(For experts, an optional challenge for novices)
A boolean function in disjunctive normal form (DNF) has the form
Z1 OR Z2 OR Z3 ...
where Z1,Z2 are "products" of "literals" (x_{i} or its negatin NOT x_{i}) .
For example
(x1 AND (NOT x2) AND x3) OR ( (NOT x1) AND x2) OR ( (NOT x1) AND (NOT x3))
By comutativity we can represent such clause as a set of integers with a positive integer i
representing the varibale x_{i} and the negative integer i representing its
negation NOT x_{i} , and the whole expression as a set of such sets.
For example the above Boolean expression can be written as
{{1,2,3},{1,2},{1,3}}
Write a Maple procedure, DNFtoBF(n,DNF),
similar to BF(n) that inputs a positive integer n and
a Boolean expression in Disjunctive Normal Form and outputs the Boolean function
it represents as a subset of nCube(n).

(A Challenge for everyone)
Write a Maple procedue BFoDNF(n,f) that inputs a Boolean function of n variables,f, given in terms of
its truth vectors, as a subset of nCube(n), and outputs a disjunctive normal form
that represents it.

(for experts, an optional challenge for novices)
Write a program that inputs positive integers n and m and outputs a random Boolean expression
in Disjunctive Normal Form with m clauses, where each clause has exactly three different literals.
Programs done on Monday Jan. 31, 2011
Jan31.txt ,
Contains the procedures of Jan27.txt (and of course Jan24.txt)
as well as the following new procedures:

RandTriple(n): a random 3element subset of {n, ,,, ,1} union {1, .. n}

RandDNF(n,m): inputs pos. integers n and m
and outputs a DNF with n variables (1, ..,n )
and m clauses, with each clause having three
literal. i denotes not x[i], and
written as a set of triplets
e.g. {{ 1,3, 4}, {5,7,8}} stands for
(x1 AND (not x3) AND x4) OR (x5 and x7 and not x8)
(Note, one can use it also to generate a random CNF, with
the dual interpretation of course)

DNFtoBF1(n,d): inputs a positive integer n and
a clause (y1 AND y2 AND ...) where y1, y2 are either
variables or their negations, and computes the
Boolean function that it represents.

DNFtoBF(n,d): inputs a pos. integer n and
a DNF d in n variables (in the above format as
a set of sets) and outputs the Boolean function
it evaluates

CNFtoBF1(n,d): inputs a positive integer n and
a clause (y1 OR y2 OR ...) where y1, y2 are either
variables or their negations, and computes the
Boolean function that it represents.

CNFtoBF(n,d): inputs a pos. integer n and
a CNF d in n variables (in the above format as
a set of sets) and outputs the Boolean function
it evaluates

SAT(n,c): A program that inputs a pos. integer n and
a CNF in n variables (represented as a set of sets as above)
and outputs true if and only if c is satisfiable.
It solves a million dollar problem
(unfortunately not in poly time).
Homework for Monday, Jan. 31, class (due Feb. 3, 2011)
All homework should be handedin on paper at the beginning of the
next class.

(For novices only)
Read and do all the examples, plus make up similar ones,
in pages 90120 of Frank Garvan's awesome Maple booklet.
[Hand in a printout of two pages with sample commands]

(For everyone) Read and understand the first two pages of
Uri Zwick's article that I handedin today.

(For experts, optional challenge for novices)
Procedure nCube(n) inputs a pos. integers and outputs
the set of all vectors with n components
consisting of {false, true}. Write a procedure
nCubeList(n) that outputs all these vectors arranged in
alphabetical order (f before t).

(Challenge for everyone, $2 to be divided among correct solutions)
Write a similar procedure, nCubeH(n)
that also returns the list of all vectors, but in a Hamiltonian
path way, in other ways, unlike the lexicgoraphic list, any
two consecutive vectors in the list should differ in only one component.
For example a legal output of nCubeH(2) could be
[[f,f],[f,t],[t,t],[t,f]]

Do some experimental mathematics with CNFs. Write a program
CNFEx(n,m,K) that inputs positive integers n,m, and K, and
generates K random 3CNFs (i.e. CNFs where each clause has at
most 3 literals), and then applies SAT(n,c) and counts
what fraction out of these K CNF's is satisfiable.

Using the previous procedure, write a super program Super CNFEx(n,M,K),
that does the above for all m from 1 to M, and outputs the
list of fractions of satisfiable CNF's for m from 1 to M.
What is the output of
CNFEx(5,100,1000);?
CNFEx(10,100,1000);?
Can you find some trends?
Programs done on Thurs. Feb. 3, 2011
Feb3.txt ,
Contains the procedures of Jan31.txt
as well as the following new procedures:

BFtoDNF1(s): inputs a Boolean function with a single member
given as the set
of ntuples that evalue true, and outputs
the subset of {1,2,...,n) union {1, ..., n)

BFtoDNF(S): inputs a pos. integer
and a Boolean function S given as the set
of ntuples that evalue true, and outputs
a disjunctive normal form for it

DNFtoSLP1(n,s): inputs a single conjunction
written as a set of integres from n to n
and outputs an SLP just for that
[under constuction]

DNFtoSLP(n,S): inputs a DNF in n variables
S and putputs an SLP that computes it
[Not done yet!]
Homework for Thurs., Feb. 3, 2011 class (due Feb. 7, 2011)
All homework should be handedin on paper at the beginning of the
next class.

[For everyone]
A Boolean funcion is symmetric if permuting the variables does not change it.
How many symmetric Boolean functions of n variables are there?
Write a program that inputs n and outputs all symmetric Boolean functions,
represented in our data structure, as a set of ntuples of truefalse.

[For everyone]
Finish up procedure DNFtoSLP1(n,s). Right now it only handles sets s (i.e. clauses) with two elements.

[For experts, challenge for novices]
WriteDNFtoSLP(n,S), by "combining" SLPs by renumbering the gates, and then ORING the respective output gates
(the last gate in each of the SLPs obtained from DNFtoSLP1(n,s)

[For experts, challenge for novices]
Define a "world history" as a list of m Eves nmumbers 1, ..., m and n Adams numbered 1 ... n,
where people never die.
At any given time any Female can mate with any Male and produce either a new Male or a new Female.
Represent the world history as a list of triples where [1,i,j] or [1,i,j] where 1 means Female
and 1 means Male, and i is the Mother and j is the father, and i and j are already living people.
Of course i should be Female and j should be Male.
For example
[1,1,[1,1,2],[1,1,2],[1,1,2],[1,1,4]]
is a world history with six people. One Eve, One Adam. The first two children of Adam and Eve were boys,
and the third one was a girl. Then Adam mated his second daughter and a boy won born, the sixth oldest person in the world.

Write a program WH(m,n,K) that generates ALL the possible legal world histories with m Eves and n Adams and
K people altogether. Find whether the sequence {nops(WH(1,1,K))} is in Sloane.

Write a program RWH(m,n,K) that generates a random world history with m Eves, n Adams and K people altogether.
Programs done on Monday, Feb. 7, 2011
Feb7.txt ,
Contains the procedures of Feb3.txt
as well as the following new procedures:

DNFtoSLP1(n,s): inputs a single conjunction
written as a set of integres from n to n
and outputs an SLP just for that

RenumberTriple(n,T1,c): inputs a single gate
T1 a triple [FunctionNumber,PreviousGate1,PreviousGate2]:
and renames the noninput arguments by adding c to them

Marry(n,L1,L2):
Marries SLPs L1 and L2 with n inputs gates
and constructs a new SLP that computes the
OR of their respective outputs

DNFtoSLP(n,S): inputs a DNF in n variables
S and putputs an SLP that computes it:
[Not yet done]
Homework for Monday, Feb. 7, 2011 class (due Feb. 10, 2011)
All homework should be handedin on paper at the beginning of the
next class.

Write procedure DNFtoSLP(n,S), by iteratively "marrying" the SLPs generated by
DNFtoSLP1(n,s) for the members s in S.

Write a program RandBF(n,K) that inputs positive integers n and K (between 0 and 2^{n}) and outputs
a random Boolean function on n variables, and K truthpoints.

Read carefully pages 119123 of Chapter 5 of Ingo Wegener's book that I handedin today.

Read carefully the wikipedia entry on
QuineMcCluskey algorithm

[Challenge for everyone!]
Implement the QuineMcLuskey algorithm.
Write a Maple program that inputs a Boolean function (as a set of nvectors of t's and f's) and
outputs the set of all prime implicants. Represent a prime implicant as we do,
as a set of integers in {1,..n, 1, ..., n} where i denotes x_{i} and i denotes NOT x_{i}.

Using the above program to constuct the matrix, expressed as a list of lists, such that
with rows labelled by prime implicants and columns by members of the Boolean function (the nvectors of t's and f's)
such that L[i][j]=1 if the jth truth vector lies in the ith prime implicant [thanks to David J. Wilson for a correction!]

[Challenge squared!]
Write a program that inputs a Boolean function and outputs as simple as possible DNF for it.
Programs done on Thursday, Feb. 10, 2011
Feb10.txt ,
Contains the procedures of Feb7.txt
as well as the following new procedures:

DNFtoSLP(n,S) inputs a DNF in n variables
S and putputs an SLP that computes it

Join(s1,s2)

OneStepQM(S): Given a set of implicants S with all of the same
size, outputs all those implied by them with one
of lower size

RandBF(n,K): a random Boolean function with n variables
and K truth vectors:

Implicants(n,f): inputs a positive integer n
and a Boolean function f in n variables
(expressed as the set of its truth vectors)
outputs a list whose ith component are
the i1 dimensional implicants (and hence having
ni+1 elements

Homework for Thursday, Feb. 10, 2011 class (due Feb. 14, 2011)
All homework should be handedin on paper at the beginning of the
next class.

Some of you have already met the challenge of writing your own
QuineMcLuskey implementation, but continuing with what we did in class,
use Implicants(n,f) to write a program PrimeImplicants(n,f)
that inputs a positive integer n and a Boolean function f,
and outputs the list whose ith item is the set of prime implicants
of dimension i1.
(Hint, the last entry of Implicants(n,f) (that is nonempty)
consists of all prime implicants. Any superset of any of these
that happen to reside on one of the entries to the left is
automatically not prime, so you can kick them out. Keep going
from right to left.

Write a program, QM(n,f) that inputs a pos. integer n and a
Boolean function f, and outputs a (hopefully) optimal or nearoptimal
minimal DNF for it.
(Hint: of course it is a subset of the set of prime implicants.
If there are points (alias truthvectors) that are only contained
in ONE prime implicant, the corresponding primeimplicant should
be definitely picked. Once you picked these prime implicants
(containing at least one point that does not have any other
affiliations), look at the remaining one, and use a greedy algorithm
to cover, at each step, as many as possible points of the Boolean function.

choose(nCube(n),a) will give you all the Boolean functions
of n variables with a truth vectors.
Write a program, ImplicantAve(n,a,i) that inputs a positive
integer n, a positive integer a between 1 and 2^{n},
and a positive integer i between 0 and n,
and finds the
average number of idimensional implicants (NOT prime implicants)
amongsts all such Booean functions.
Of course Implicants(n,a,0) should always be a.

($5 to be divided among all correct entries)
Using the numerical output of ImplicantAve(n,a,i)
for various (small, and not small, n, a, and i=1,i=2, i=3...)
Conjecture an explicit (closed form) expression
for ImplicantAve(n,a,i).

($10 to be divided among all correct entries)
Use human ingenuity to prove your conjecture rigorously.
Added Feb. 14, 2011: Congratulations to Matthew Russel and C.K. Lee for winning these prizes.
They each get (5+10)/2=7.5 dollars! Read
Matthew Russel's pretty proof
(here is Matthew Russel's testing),
and CK Lee's pretty proof .

(Three chocolate Valentines for the three best entries, to be
posted here)
Every year, before Feb. 14, 2011,
I assign a problem, due Feb. 14, 2011,
whose solution is shaped like a Valentine
(but the students do not know that).
So I make up problems whose solutions are
sometimes a
Cardioid,
and sometimes the
Mandelbrot set,
and then I ask students to print the shape up and cut it out,
and submit it as mandatory homework.
This year I ran out of ideas, so here is a contest
for the best entry, using Boolean functions (?) or otherwise
whose answer is either one of the two above shapes, or another
Valentinelike shape.
Programs done on Monday, Feb. 14, 2011
The program file has gotten to big to handle.
I have converted it into a Maple package with builtin help
Boole.txt.
I have added a few more procedurs, making progress on QuineMcluskey,
but not yet finishing it. I hope that we can finish it next time.
Homework for Monday, Feb. 14, 2011 class (due Feb. 17, 2011)

Study the new procedures: PrimeImplicants and QMCrucial in the Maple package
Boole.txt.
Note that QMCrucial returns the crucial subset of the the set of prime implicants, that
must be there, followed by the leftover points (not covered by these), and the leftover
primeimplicants. Try to understand what is going on.

[Challenge]
Think of a greedy algorithm that takes the leftover prime implicant that
covers the most of new points each time, until it runs out of points, and
RETURNS a simplified DNF for the input Boolean Function.

[Challenge]
A Bruteforce approach to the same problem, that guarantees optimality
(alas at an exponential cost) is to examine all possible subsets
of the set of leftover prime implicants (if there m prime implicants, there 2^{}1 possible
nonempty sets. Find out which of these cover the leftover points, and amongsts those that
do cover all these points, pick the "cheapest" one.

Check empirically as many as possible of the Amer. Math. Monthly problems I handed in today from
the Feb. 2011 issue.

[up to $5 prize for EACH] Try to prove, using Maple, rigorously as many of these problems.
If you cheat and use paperandpencil and/or human ingenuity, you may get a part of the $5.
Programs done on Thursday, Feb. 17, 2011
Today we started a new package
PIE.txt,
using InclusinExclusion arguments to prove satisfiability
(or rather the complement problem, deciding when a given DNF is
a tautology).
So far we only have:

PIE(L): inputs a list of sets, L, and outputs the number
of elements in their union
for example, try: PIE([{1,3},{2,3}])

AND1(C1,C2,n):
Inputs two clauses, C1 and C2, in n variables (expressed
as sets of integers from the set {n,...,1,1,...,n}) finds
their AND
Homework for Thurs., Feb. 17, 2011 class (due Feb. 21, 2011)
 Using AND1(C1,C2,n) repeatedly write a procedure
AND(L,n) that inputs a list of ANDclauses and
outputs
L[1] AND L[2] AND ... L[nops(L)]

write an adaptation of PIE(L), PIEdnf(n,S)
that inputs a pos. integer n and a DNF S, expressed as
a set of ANDclauses (each of which is a set of positive and negative
integers, of course without any integer cohabiting with its negative)
and outputs the NUMBER of truthvectors (alias points in the ndimen.
unit cube) that belong to it divided by 2^{n}.
(Hint: instead of nops you have the weight of a clause, that is
(1/2)^{nops(Clause)}. Indeed, the fraction of points in
a DNF with one literal (e.g. x_{1} is 1/2), in
two literals is 1/4 etc.

Using PIEdnf(n,S)
write a oneline program IsTaut(n,S) that inputs a pos. integer n and a DNF
S and outputs true iff S is a tautology.

By using RandDNF(n,m) of
Boole.txt for many n and m, and DNFtoBF(n,S),
experiment to see what is faster?
IsTaut(n,S) or evalb(DNFtoBF(n,S)=2^n)

[$10 prize] Write a procedure P11552(); that uses the many
procedures of
RENE to prove Amer. Math. Monthly 11552.
If I like it, it would be added to the next version of RENE,
and your name(s) would be mentioned.
Programs done on Monday, Feb. 21, 2011
We continued and have a new version of
PIE.txt,
with the following new procedures:

AND(L,n): inputs a set of clauses and finds their AND

PIEdnf(L,n): A fast version of PIEdnf(L,n)
quits as soon as it is obvious one way or the
other inputs a DNF (with our format as a set
of sets) and a pos. integer n, and outputs the
the number of truth vectors (in the truth table)
divided by 2^n (if the ans. 1 it is a tautology)
For example, try: PIEdnf({{1,2},{3}},3);

PIEdnfF(L,n): A fast version of PIEdnf(L,n)
Using the Bonfferoni inequalities
(truncated PIE)
Homework for Mon., Feb. 21, 2011 class (due Feb. 24, 2011)

Write a new version of RandDNF(n,m), call it RandDNF3(n,m)
that inputs pos. integers n and m and outputs a random DNF
in n variables and exactly m clauses
(expressed in our format as a set of sets) where each clause (member set)
has exactly three literals. For example, you can't have
2clauses, like {1,2}, and 1clauses, like {3}. Of course,
you should not have i and i in the same clause
(e.g. {3,3,1} should not be allowed).
For example one possible output of RandDNF(3,4) could be:
{{1,2,3},{1,2,3},{1,2,3},{1,2,3}}.

Write a program TestPIEdnf(n,m,K) that inputs
pos. integers n,m, and K, and generates, K times,
a random 3DNF, and runs PIEdnf on it. It should output
the number of 3DNF's that are tautologies, and the number
that are not (obviously they should add up to K).
Fix n=4, and experiment for m between 1 and 15. How does this
number change?

Modify PIEdnfF(L,n), call it PIEdnfF1(L,n),
that also returns the i, i.e. stage in the InclusionInclusion
where we quitted for sure with either knowing that
it is a tautology or not.

Write a program TestPIEdnfF1(n,m,K,x) that inputs
pos. integers n,m, and K, and generates, K times,
a random 3DNF, and runs PIEdnfF on it,
and outputs
the number of 3DNF's that are tautologies, and the number
that are not (obviously they should add up to K),
and a list, let's call it M, such that M[i] is the number
of 3DNFs that exited at stage i of the PIE.

Shame on you for not reading carefully and understanding
both two proofs demanded in the popquiz (about half of you were able to reproduce the first proof).
Please read and understand pages 119123 in
Ingo Wedener's book "The Complexity of Boolean Functions"
that I handed in a few weeks ago.
(There will be another pop quiz, sometime in the future,
and I hope that you will do better next time!)

Read pp. 4750 of the
Bill Gates and Christos Papadimitriou masterpiece
as well as the complete
Colvey RoneyDougal and Vince Vatter's awsome article
Programs done on Thursday, Feb. 24, 2011
We started a new package
FP.txt,
to study flipping panckages. So far it contains the following
procedures (that many of your wrote yourself, but here is the
official version, contributed by David J. Wilson)

Flip(L,i): takes a permutation L as a list of integers
and 'flips' the first i entries

NS(L):Inputs a permutation L as a list of integers and
naively sorts them by searching for the largest integer
not in its correct place, flips that integer to the front
of the list and then flips the front of the permutation
to place it correctly.
Outputs a list of the positions where flips were carried out at

FindElement(i,L):Inputs an element i and list L and outputs
the position of i in L. If i is not in L, no output.

NSSteps(L):Inputs a permutation L as a list of integers and
outputs the number of steps in the naive sort method NS(L).
Homework for Thurs., Feb. 24, 2011 class (due Feb. 28, 2011)

Write a program Shells(n) that inputs a positive integer n and outputs a list
whose ith entry is the set of all permutations that can be reverseprefix sorted
with i steps (but not less). The union of all the entries of the outputlist should be permute(n),
and its nops (number of entries, i.e. its length) is the quantity f(n).

Using the above procedure, with option remember, write a program,
Bill(n,i), that inputs pos. integers n and i and outputs the number of
permutations of length n that are prefixsortable with i flips.
See whether the sequences {Bill(n,1)}, {Bill(n,2)}, etc. are in Sloane.

($5) prove the generating function, attributed by Sloane to Flajolet,
for the number of adjancencyless permutations.

Read (and understand!) pp. 4950 of the
Bill Gates and Christos Papadimitriou masterpiece.

Program the sorting in Fig. 1.
Programs done on Monday, Feb. 28, 2011
The first half of the class was "wasted" when
students tried to follow my stupid approach to
prove by computer Amer. Math. Monthly Problem
11558 (March 2011, vol. 118, p. 275, proposed by Amdrew McFarland)
Given four concentric circles, find a necessary and sufficient
condition that there be a rectangle with one corner on each circle.
As Susan Durst (and possibly other people), it is more efficient
to start with the rectangle, and look at the distances (or rather
distancesquared) from the center to the vertices.
We also wrote the short file
Max.txt and
compared the naive algorithm for finding the maximum of
a list of numbers (see MaxSlow below) to a "fast" approach
(see MaxFast below)
that turned out, at least empirically, to be much slower.
The two procedures are:

MaxSlow(L): inputs a list of real numbers L and
outputs the place where it has a maximum and
the value there

MaxFast(L): a "fast" version of MaxSlow(L) that is
much slower
Homework for Mon., Feb. 28, 2011 class (due March 3, 2011)

Use Susan Durst's (and Yu Wang's) approach for solving the above
Monthly problem
by first empirically
conjecturing a necessary condition for the four distancessquared
from a point (x,y) to a the four corners of a rectangle, that
without loss of generality are the points (0,0), (a,0), (0,b),
and (a,b), by writing a program P(a,b,x,y) that inputs four real
numbers a,b,x,y and outputs the fourtuple of distancessquared.
By pluggingin several spefic numeric values for a,b,x,y
try and find the neccessary condition

(5$ to be divided) by using human (and/or computer) ingenuity, prove rigorously
that necessary condition, and also prove that it is sufficient.

(5$, to be divided) analyze the computational complexity
of MaxFast(L) and prove that Dr. Z. is stupid, and that
the theoretical computational complexity of MaxFast is
not any better than MaxSlow(L). It still remains to be
understood, why it is so much slower.

Write a program adj(pi) that inputs a permutation pi and
outputs the number of adjancies of pi, where having the
largest element at the end counts as an adjancency.

Using adj(pi),
write a heuristic greedy algorithm, GS(pi), for prefix sort, that
hopefully would require less flips than NS(pi) (Naive sort),
that inputs a permutation pi, and
and alway chooses a flip in such a way as to increase
the number of adjancies, if possible, and otherwise,
picks at random a flip that does not decrease that number,
and if even that is not possible (but it probably can never happen)
picks at random any flip. Keep going until you have nops(pi)
adjancies. The output is the list of places where the flip occurs.

Write a program TestGS(n,K) that inputs a positive integer n and
a positive integer K and picks K random permutations of length n,
and finds the average and standard deviation of the number
of flips outputted (i.e. nops(GS(pi))).
What did you get for TestGS(10,1000)? For TestGS(20,1000)?
Programs done on Thurs., March 3, 2011
BC.txt containing the following procedures:

Flip(pi,i): flips the ith pancake, or more
formally, inputs a permutation pi and reverses the
first i entries.

Neis(pi): all the immediate neighbors of a permutation pi,
in other words, the set of permutations obtained from pi
by performing one flip.

Shells(n): inputs a pos. integer n and outputs
a list whose ith entry is the set of
permutations of {1, ..., n} who need at least i flips

adj1(pi): the number of adjancies of pi
(if n=nops(pi) is at the end, it counts as an adjancy)

Children(P): all the pairs [pi,L]
(where pi is a permutation and L is a list of flipplaces,
where the children are richer than the parent
For example, the Children of
[[2,4,1,3],[]]
are {[[4,2,1,3],2], [[1,4,2,3],3]}

WLS(pi): All the wasteless prefix sorting sequences
Homework for Thurs., March 3, 2011 class (due March 7, 2011)

Let a[i] be the number of permutations on {1, ..., i} that allow
a wasteless prefix sort (in other words, those pi for which WLS(pi) yields the identity permutation.
Write a program nuWL(n) that inputs a positive integer n and outputs the first n terms of that sequence.
Comute nuWL(8) and check whether it is in Sloane.

Write a program aWLS1(pi,r) that inputs a permutation pi and outputs all the permutation that
allow a wasteless sort until the rth flip, then at the rth flip, performs a flip that does not
increase the number of adjancencies (but does not decrease it either), and then keep going
with wasteless flips until it gets stuck (or gets completely sorted).

Let b[i] be the number of permutations on {1, ..., i} that allow
an almost wasteless prefix sort (i.e. it gets completey sorted by aWSLS11(pi,r) for some r between 1
and adj1(pi)+1) and that are not sortable with WLS(pi).
Write a program nuaWL(n) that inputs a positive integer n and outputs the first n terms of that sequence.
Comute nuaWL(7) and check whether it is in Sloane.

Let t(pi) be the first element of a permutation pi, for example t([3,1,2,5,4])=3. Let B0(pi) be its first
block, for example t([3,2,1,5,4])=[3,2,1], and t([2,3,5,1,4])=[2,3].

Let a0(pi) be 0 if the first block is a singleton

Let a0(pi) be 1 if the first block is increasing

Let a0(pi) be 1 if the first block is decreasing
Let tp be the entry adjacent to the largest entry of B0(pi), and let
tm be the entry adjacent to the smallet entry of B0(pi) (one of them is t+1 or t1),
let B1(pi) be the block containing tp and let Bm1(pi) be the block containing tm.
Call the block B0(pi) block 0, the block B1(pi) block 1, and the block Bm1(pi),
block 1. Of course block 0 must come first, but sometimes block 1 is to the left of block 1
and sometimes it is the other way. So the two possibilities are
[0,1,1] and [0,1,1]
Each individual block is either a singelton, increasing, or decreasing. Indicate this information
by 0,1, and 1 respectively. If block i (i=0,1,1) is increasing write this is as [i,0] etc.
The type of a permutation is either
[[0,c1],[1,c2],[1,c3]] (where each of c1,c2,c3 belong to {1,0,1})
(when block 1 came to the left of block 1) or
[[0,c1],[1,c2],[1,c3]] (where each of c1,c2,c3 belong to {1,0,1})
(when block 1 came to the left of block 1) . If one of the blocks is nonexistent (e.g. when the first block
is the singelton 1 or the singleton n) then we only have either [[0,c1],[1,c2]] or[[0,c1],[1,c3]].
Call these triple (or pair) of pairs the type of the permutation. Write
a program, Type(pi), that inputs a permutation pi and outputs its type.
Programs done on Mon., March 7, 2011
Strassen.txt containing the following procedures:

IsMatrix(A): inputs a list of lists of numbers and decides
whether it is a legal matrix. For example
IsMatrix([[1,2],[3,5]]); should output "true" while
IsMatrix([[1,2],[3,5,8]]); should output "false".

MP(A,B): inputs two matrices A and B
given as a lists of lists, and such that
nops(A[1])=nops(B) and outputs the matrix
product AB, also represented as a list of lists of numbers.

NP2(a,b): naive multiplication of 2digit integers a and b.
NP2(11,12); should give 132.

NRP(a,b): naive RECURSIVE multiplication of a and b,
where and b are arbitrary positive integers.
Homework for Monday, March 7, 2011 class (due March 10, 2011)

Modify NRP(a,b) and write a program CRP(a,b) (Clever Recursive product),
using the deep identity
ad+bc=(a+b)(c+d)acbd

By using time();,
experiment, with very large integers a and b,
(generated randomly)
whether CRP(a,b) is significantly faster than NRP(a,b).

(Small Challenge) Write a program RMP(A,B) that does matrix
multiplication recursively, but using the obvious eight
multiplications. Check whether it gives the same answer
as MP(A,B)

(Challenge, I'll be proud of you!)
Look up (in wikipedia or elsewhere) the Strassen algorithm,
that uses seven multiplication in every recursive step,
and implement it.
Added March 10, 2010: Quite a few people met the challenge. For example, see
Simao Herdade's Strassen code
Programs done on Thurs., March 10, 2011
CB.txt containing the following procedures:

WhatType(pi): [INCOMPLETE, and using a complicated approach (see homework below)] inputs a permutation and outputs its
type (a triple (or pair)) of pairs indicating
whether the first block (block #0) is a singleton (0) increasing
or decreasing, and similarly for block #1 (the block
of integers immediately larger than the first block etc.
for example, WhatType([2,3,5,4,1,6]) should be
[ [0,1],[1,1],[1,0]], and retunrs the "parsing"
[[2,3],[5,4],[1]]

FindBlock(pi,a): [Incomplete!]
inputs a perm. pi and an integer a finds
the block that it belogs to and whether
it is a sinleton (0), increasing (1) or decreasing (1)
For example,FindBlock([2,3,1,4,5,6,7,8],5); should return
[4,5,6,7,8],1
Homework for Thurs. March 10, 2011 class (due March 21, 2011)
Andrew Baxter pointed out that the approach that I suggested for WhatType(pi) and FindBlock(pi,a) was
unnecessarily complicated. It is much better to do the following approach suggested by him.

Write a procedure BreakUp(pi) that inputs a permutation pi and outputs the list of blocks.
For example, BreakUp([5,4,1,2,7,6,3,9,8]); should return the list
[[5,4],[1,2],[7,6],[3],[9,8]]

Using BreakUp(pi) write a new version of WhatType(pi)

Write a procedure Types(n) that inputs a positive integer n and outputs
the set of possible types that permutations of [1,n] can have.

Write a procedure HowMany(n) that inputs a positive integer and returns a table
indicating how many permutations of {1, ..., n} belong to each of the types.

Have a nice and relaxing Spring Break!
Programs done on Monday, March 21, 2011
Spring11.txt containing the following procedures:

FirstBlock(pi):
inputs a permutation pi and outputs the first
(consectutive) block (may be a singleton) written
as a list, and the leftover.
For example, FirstBlock([5,4,1,2,3]);
should yield [5,4] , [1,2,3].

BD(pi): inputs a permutation pi and outputs its
decomposition into (consec.) blocks. For example
BD([2,3,5,4,6,1]); should be
[[2,3],[5,4],[6],[1]];

SimaoHerdade(B):
inputs a list of numbers and outputs 0 if it
is a singleton, +1 if it increasing and 1 if
if it decreasing

FindBlock(L,a): inputs a list of lists and
a number a and outputs the place of the
list containing a, or returns FAIL
For example, FindBlock([[3,4],[1,5],[6,7]],5);
should return 2.

WhatType(pi): inputs a permutation pi and outputs
its type in the format of (usually) triplet
of pairs [1,0],[1,1],[1,1],[0,0],[0,1],[0,1] etc.
e.g. [1,0] is the block of the elements immeidately
smaller than the leftmost block and the [0] in [1,0]
means that it is a singleton. If it would be increasing
it would be labelled [1,1], and decreasing [1,1]
Homework for Mon. March 21, 2011 class (due March 24, 2011)

Procedure WhatType(pi) only tells you the relative placement of
what we called "block +1" and "block 1", but why stop there.
(Recall that block +1 consists of numbers that are just above
the entries of block 0, and
block 1 consists of numbers that are just below.
One can define WhatType2(pi) that does the same for blocks
+2,+1,1,2. Modify WhatType(pi), and write a procedure,
WhatType2(pi), that outputs a list of (up to) length 5 that
gives you this type2. For example,
WhatType2([5,7,1,3,4,2,6]); should yield (I hope!)
[[0,0],[2,0],[1,1],[2,0],[1,0]].

Ditto for WhatType3(pi).

(Challenge!) Write a program gWhatType(pi,a) that inputs
a permutation pi and a pos. integer a, and outputs a list
of size ≤ 2a+1 that describes the relative placments, and
the status (singleton, increasing, or decreasing) of pi.
gWhatType(pi,1) is the same as WhatType(pi),
gWhatType(pi,2) is the same as WhatType2(pi),
and
gWhatType(pi,3) is the same as WhatType3(pi).

Write a procedure BestFlips(n) that inputs a positive integer n,
and outputs a table such for any permutation pi, of length n,
T[pi] is an optimal sequence of flips. For example,
if T2:=BestFlips(2), then
T2[[1,2]]=[] and T2[[2,1]]=[2]
If T3:=BestFlips(3) then
T3[[1,2,3]]=[], T3[[2,1,3]]=[2], T3[[3,2,1]]=[3],
T3[[312]]=[3,2], T3[[2,3,1]]=[2,3], T3[[1,3,2]]=[2,3,2] .
(Hint: go backwards. Of course T[IdentityPermutation]=[], then
gather those that are "distance 1" from IdentityPermutation,
and record where the flip occurs, then those of "distance 2",
not yet encountered etc.
Programs done on Thursday, March 24, 2011
Today' class is dedicated
in loving memory of
Philippe FLAJOLET
(Dec. 1, 1948 March 22, 2011)
(see also wiki)
studying his great expository
article on Singular Combinatorics
(based on his ICM 2002 invited talk)
and his seminal
article on inherently ambigious formal languages.
Today we wrote the file
flajolet.txt containing the following procedures:

Test1(a,N): inputs a real number and outputs
the ratio of the coeff. of z^n in (1z)^(a)
by n^(a1)*Gamma(a) for n from 1 to N

Test2(a,b,N): inputs a real number and outputs
the ratio of the coeff. of z^n in
(1z)^(a)*(log(1z)/z)^b
by n^(a1)/Gamma(a)*log(n)^b for n from 1 to N

Test3(N): tests example 2 in P. Flajolet's ICM 2002 paper

Shar(N) the first N Catalan Numbers

GuessAsy(L,a): conjectures, using Least Squares,
a constant beta such that
M[n]:=L[n+1]/L[n]/a^n is asymptotic to
C*(n^beta) for some constant C by "fitting"
log(C)+ beta*log(n)=log(M[n])

s(z,N): the first N terms of the Maclaurin
series of s(z) in Flajolet's 1985 paper, bottom of p. 7
Homework for Thurs. March 24, 2011 class (due March 28, 2011)

Write procedure Test3(n),
testing Example 2 on page 564 of
Philippe Flajolet's article on Singular Combinatorics

Write a procedure TestExample1(N) ,
testing Example 1 on page 564 of
Philippe Flajolet's article on Singular Combinatorics

Modify procedure Shar(N), call it Shark(N,k) to crank out the first N terms of the Maclaurin expansion
of the unique formal power series
f(z)=1+z*f(z)^{k}
(Note that Shark(N,2) is Shar(N))

(Challenge!)
Guess the asymptotic behavior a(n)=Ca^{n}n^{β} of the sequence
Shark(N,3), and Shark(N,4), except for the C.

(Big Challenge!)
Guess the asymptotic behavior a(n)=C*a^{n}n^{β} of the sequence
Shark(N,k), including the C! Prove it!

Fix procedure s(z,N).

(Challenge!)
Write a procedure HNY09(N) that inputs a positive integer N, and verifies
the correctness of K_{ν} for ν=1...N, with the given
d_{n} in the infinite continued fraction on the right in
Philippe Flajolet's lovely 2009 Happy New Year card
(Note: as far as I know this is still a conjecture!)
Programs done on Monday, March 28, 2011
Today we wrote the file
Mar28.txt
culminating in a bruteforce, but optimal,
algorithm for prefixsort. A slight modification
produced
Mar28a.txt
that does the analogous job for stacks of burnt pancakes
(alias signed permutations).
The
first file

flip(pi,i): inputs a permutation pi and outputs the
permutation obtained by flipping the first i entries

Ball(pi,k): all the permutations of distance ≤ k from pi

Spehere(pi,k): all the permutations, followed
by the list of flips, of exact distance k from pi
For example, Sphere([2,1],1); should
output {[[1,2],[2]]};

BFPF(pi): inputs a permutation pi and
outputs ONE OPTIMAL list of flips making it
[1, ..., nops(pi)]

f(n): the largest number of flips needed to sort any
stack of (unburnt) pancakes.

fSeq(N): the first N terms of the sequence f(n), Sloane A058942
The
second file
contains all the above, adapated to signed permutation,
except that f(n) and fSeq(N) have been renamed
g(n) and gSeq(N).
Homework for Monday March 28, 2011 class (due March 31, 2011)

Recall that a type is a list of pairs [i,j] where
i is an integer, and j is either 1 (representing a decreasing block),
0 (representing a singleton) or 1 (representing an increasing block).
For example
T=[[0,1],[1,1],[1,0]].
Define the paddedversion of a a type PD(T) to be the same
with 0s inserted beween two consective pairs (but not at
the beginning or end). For example,
PD(T)=[[0,1],0,[1,1],0,[1,0]]
Define the Sorted Version a rearrangent of the pairs
such that

all the 0's are either before or after the pairs,

Either
The first components of the pairs are increasing and
the second componets are 0 or 1
OR
The first component of the pairs are decreasing and then
the second componets are be all 0 or 1
Write a program IsSV(T,T1) that inputs a type T and a list T1
of pairs and 0s
and outputs true if and only if T1 is a sorted version of PD(T).

Adapt BFPF(pi) to write BFPFtype(T) that inputs a type,
and outputs an optimal list of flips, applied to PD(T) that
leads it to a sorted version.

Translate the diagram on p. 50 of the
Bill Gates and Christos Papadimitriou article
into the new notation, and apply
BFPFtype(T) to each of the sixteen types displayed, and check
if your computer got the same things that Bill Gates got doing
it by hand.
Programs done on Thurs., March 31, 2011
Today we wrote the file
Mar31.txt
that contains all the procedures of Mar28.txt, and in addition:

Pad(T):
inputs a type (a list of pairs) and outputs
the same list with 0's between any consecutive
entries. For example Pad([[1,1],[3,1],[2,1]]);
should be [[1,1],0,[3,1],0,[2,1]];

IsSV(L): inputs a padded type and checks
whether it is "sorted"
(i): All the 0's must be at the beginning or the end
(ii) the first elements of the pairs must be either
increasing (and then the second elemets must all be
0's or 1's or
decreasing (and then the second elements must all be
0's or 1's. For example
IsSV([0,0,[1,1],[2,1],0,0]); should be true
IsSV([0,[1,1],[2,1],0]); should be false

BFTF(T): inputs a type T and
outputs ONE list of flips making it
a sorted version
[Under Construction!]

flipT(T,i):
flips a padded type at the ith location, for
example flipT([0,[1,1],0,[2,1],0,[3,1]],4);
should be [[2,1],0,[1,1],0,[3,1]]

SphereT(T,k): all the padded types, followed
by the list of flips, distance k from T
For example, Sphere([[2,1]],1); should
output {[ [[2,1]],[1]]};
[Under Construction]
Homework for Thursday March 31, 2011 class (due April 4, 2011)

Finish up BFTF by first finishing up SphereT, writing BallT (the type analog of Ball),
and whatever it takes.

[If you haven't done it already in the March 28, 2011 homework]
Translate the diagram on p. 50 of the
Bill Gates and Christos Papadimitriou article
into the new notation, and apply
BFTF(T) (formerly called BFPFtyle) to each of the sixteen types displayed, and check
if your computer got the same things that Bill Gates got doing
it by hand.

(Chanllenge, 5 dollars to be divided among all correct answers to EACH problem)
Do as many as possible of the American Mathematical Monthly problems of the April 2011 issue,
using Maple as much as possible. It does not have to be completely computergenerated,
but it would be nice if you use Maple experimentations to conjecture and/or suggest
a solution.
Added April 5, 2011: Andrew Baxter and Matthew Russell, independently solved
David Callan's AMM probelm 11567, and shared a $5 prize.
Read Andrew Baxter's
brilliant solution. I hope to soon post Matthew Russel's equally brilliant solution.
Justin Gilmer solved Kurt Bresniker and Stan Wagon's AMM problem 11569. I hope
to post his solution soon.
Programs done on Monday, April 4, 2011
In the first part we had a belated celebration of "π day",
exploring the amazing website of the laterdayRamanujan,
Jesús Guillera,
and had a context who would code fastest the top formula in his
hopepage. Andrew Baxter won 1 dollar, and Taylor Burmeister came second
and won 25 cents. Matthew Russel also came close.
The second part was back to pancake flipping.
Today we wrote the file
Apr4.txt
that completed the procedures of Mar31.txt and added a new one:
GatesTypes():

BFTF(T): inputs a type T and
outputs ONE list of flips making it
a sorted version

flipT(T,i):
flips a padded type at the ith location.
For example,
flipT([0,[1,1],0,[2,1],0,[3,1]],4);
should be [[2,1],0,[1,1],0,[3,1]]

SphereT(T,k): all the padded types, followed
by the list of flips, distance k from T
For example, SphereT([[2,1]],1); should
output {[ [[2,1]],[1]]};

BallT(T,k): all the padded types of distance
≤ k from pi

GatesTypes(): The 18 types of the GatesPapadimitriou
prefixsorting algorithm.
Homework for Monday April 4, 2011 class (due April 7, 2011)

Code the first formula in
Jesús Guillera's
amazing homepage.
Try to get as many digits of Pi as possible.

Code the second (still conjectured) formula in
Jesús Guillera's
amazing homepage.
Try to get as many digits of Pi as possible.

Write a new version of procedure WhatType(pi) that inputs a permutation
pi and output its padded type, followed by a list of integers
that constitute a "translation" between the blocks and their ending
places. For example,
WhatType([5,6,7,1,2,3,4]); should return
[[0,1],[1,1]],[3,7]

(Challenge!) Using WhatType(pi) and BFTP(T), write a general
sorting algorithm, PancakeSorting(pi,Types) and inputs a permutation
pi and a list of Types, and outputs a sequence of flips that sorts it.
Programs done on Thursday, April 7, 2011
Today, we had the surprise visit of
Michael Somos,
one of the greatest experimental mathematicians alive today,
and we exlored the amazing
Somos Sequence.
Then we continuted pancake flipping.

UncleSimao(B)
inputs a list of numbers and outputs 0 if it
is a singleton, +1 if it increasing and 1 if
if it decreasing
(Note: this is identical to the previous SimaoHerdade(B),
but with a new name to reflect the happy event that made
Mr. Herdade miss classes)

Under Construction:
WhatTypeG(pi): Same as WhatType(pi) BUT
with 0's padded, and another list of
increasing pos. integers, indicating the
endlocations of the respective "blocks".
For example:
WhatTypeG([3,4,5,9,1,2,7,6,8]) should return (I hope!):
[[0,1],0,[1,1],[1,1],0],[3,4,6,8,9]
Homework for Thurs. April 7, 2011 class (due April 11, 2011)

MANDATORY (anyone who does not submit it by April 11,
would only get a B+ in the class)
Write a Maple program that implements
the breakpoint algorithm as described in Chapter 5 of the
JonesPevzner book on informatics.

MANDATORY (anyone who does not submit it by April 11,
would only get an A in the class)
Complete procedure WhatTypeG(pi), and test it out.

Using the completed WhatTypeG(pi), and using the BFTF(pi) of
Apr4.txt
write a perfixsorting program that inputs a permutation pi, and outputs
a list of places where to flip to make it the identity permutation, by first
determining the type, then invoking BFTF, then transcribing the "metainformation"
there into the actual places given by the second part of the output of WhatType(G)
and keep going until the type is [[0,1]] (one increasing block).
Programs done on Monday, April 11, 2011
We attempted to write procedure PS3(pi) that inputs a permutation pi and
outputs a list of filps indicating the places where one should flip to
get the identity permutation, implementing and generalized and streamlined (and completely auotmatic!)
GatesPapadimitriou style prefixsorting algorithm. The incomplete code is contained in
the file Apr11.txt,
that uses the following files
At the last ten minutes we investigated the Monthly problem
Kurt Bresniker and Stan Wagon's AMM problem 11569, brilliantly solved by Justin Gilmer.
The short file is contained in
Apr11a.txt,
Homework for Monday April 11, 2011 class (due April 14, 2011)

Combine all the relevant procedures that are needed from the various files mentioned above,
and use Emilie Hogan's ideas of keeping track of the blocklengths rather than the ending point,
and finish up (or start from scratch) procedure PS3(pi).
Call that ONE file MyNamePF.txt, (where MyName is your name, for example JakeBaronPF.txt) and if you are proud of it and it works
well, EMail it to me, so that I can post it.

Assuming that you have succeeded to program PS3(pi), write a Maple procedure, StatPS3(n), that inputs
a positive integer n, and outputs (i) the largest number of necessary flips using PS3(pi), amongst
all permutations pi of {1, ..., n} along with the set of "champions", as well as as the average number of flips,
for all n! permutation. Find out the output for n between 2 and 8.

(Challenge) By analyzing the data of LosingList(N) (for N=200 or whatever) in
Apr11a.txt,
repeat Justin Gilmer's feat of conjencturing, and then proving, a characterization of
all losing positions.

Read (and understand!) the first four pages of the
Noga AlonRavi Boppana masterpiece.
Programs done on Thurs., April 14, 2011
We started studying antichains in the Boolean lattice
(alias monotone Boolean functions)
Apr14.txt,
that uses the following files

AntiChains(n): The set of antichains of {1, ...n}
For example, Antichains(2):
{ {{}}, {{1}},{{2}},{{1},{2}},{{1,2}}}

CanJoin(B1,B2), can the antichains B1 and B2 joined to make
an antichain B1 union B2?

Sperner(n): the maximal size of an antichain
of n elements (by complete brute force)

IEantichanis(n): inequivalent antichains on {1, ..., n}
Homework for Thurs. April 14, 2011 class (due April 18, 2011)

A MSLP (Monotone Straight Line Program) on n variables
and m noninput lines is a list of length n+m, such that
the first n entries are x1, ..., xn, and entry k for n < k ≤ n+m
is either a pair [i,j,UNION], or [i,j,INTERSECT] with
i < j < k. The evaluation of such an MSLP is
obtained by putting in location i (1 ≤ i ≤ n)
the set of all 2^{n1} sets that contain i,
and then evaluating each line in its turn. The output is
a certain set of sets that is monotone.
Write a Maple procedure EvalMSLP(MSLP,n) that inputs such a
monotone straight line program and outputs the monotone Boolean
functions (expressed as a set of sets).

Write a program ACtoMBF(AC)
that inputs an antichain and outputs the corresponding
monotone Boolean function

Write a program MBFtoAC(AC)
that inputs a monotone Boolean function (expressed as a set of sets)
and outputs the corresponding
antichain.
Programs done on Monday, April 18, 2011
Apr18.txt,
We started to implement the constuctions and definitions in the
Noga AlonRavi Boppana masterpiece.
(Combinaorica 7(1) (1987) 122), in particular page 5.
So far we have the procedures:

Imply(R,L,W): inputs pos. integers R and L
and a list of length R of sets (of integers) W
and outputs the set of all elements that belong
to AT LEAST two of the sets in W,
if its cardinality is ≤ L OR returs FAIL if the cardinality is > L

ES(R,L,W,m): inputs pos. integers R and L,
and a list of length R of sets (of integers) W,
and a positive integer m,
and outputs the set of sets of all elements
with ≤ L elements,
that belong
to AT LEAST two of the sets in W and all their supersets in {1, ..., m}

Closure1(R,L,F,m): Inputs pos. integers R and L
and a family of sets of integers, F
and outputs ONE extra set implied by SOME
subfamily of R sets in F (still in progress)
Homework for Monday April 18, 2011 class (due April 21, 2011)

A multiset is a set of pairs {[a1,i1],[a2,i2], ...} where
i1,i2, ... ≥ 1,
and this means that a1 shows up i1 times, a2 shows up i2 times
.... Write an analog
of choose(S,k), call is Mchoose(S,k) that inputs a finite set S and outputs the
set of all multisets with k members. For example
Mchoose({1,2,3},2);
should return {{[1,2]},{[2,2]}, {[3,2]},{[1,1],[2,1]},{[1,1],[3,1]},
{[2,1],[3,1]}}

Using Mchoose, write a new version of Clusure1 that does exactly what
the AlonBoppana article intends.
Programs done on Thursday, April 21, 2011
Apr21.txt,
contains:

Mchoose(S,k): inputs a set S and a pos. integer
k and outputs the set of MULTISETS with exactly
k elements written in the format {[a1,i1],[a2,i2], ...}

Prk(F,r,k): inputs a collection of sets of integers
F, and pos. integers k and r, and outputs true of false
according to whether F has socalled property P(r,k)
in p. 5 of AlonBoppana Combinatorica 7(1)(1987) 122

NCP(A,B): The set of sets {{a1,b1}, ...}, a in A and b in B

gNCP(L): gNCP(L) given a list of sets L, constructs
all the "menues" (picking exactly ONE element from each
set in L
Homework for Thurs. April 21, 2011 class (due April 25, 2011)

Using gNCP(L), write a program ExtremePrk(r,k) that uses procedure gNCP(L) to
constant the family of all possible menuchoices from a kcourse meal, where
each course has (r1) different dishes to choose from, and all the dishes are distinct.

Check that ExtremePrk(r,k) has property P(r,k) for ALL 1 ≤ r ≤ 3 and 2 ≤ k ≤ 4

Read and understand the proof of Lemma 3.2 on p.6 of the
AlonBoppana masterpiece.

Verify empirically the statement that if F has property P(r,k) then F_{C} (as defined in the proof of Lemma 3.2)
has property P(r1,kC), by trying out various F.

(Challenge) Using what we started in
Apr18.txt,
(but now using the Mchoose to make it complete), implement the closure algorithm, call is
that inputs a collection C of sets and outputs its closure.
Programs done on Monday, April 25, 2011
Apr25.txt,
contains:

Colorings(m,g):
The set of all Colorings of {1,...m} with g colors
A coloring is expressed as a list L of length m
where L[i]=c means that vertex i is colored with color c

IsPC(CO,W): Inputs a coloring CO of {1, ...,m}
(a list of length m) and a subset,W, of {1, ...,m}
decides whether the set A is PC by CO, in other words
all the colors assigned to the members of the set A
are different

NuA(m,g,W):inputs a pos. integer g, and a pos. integers
and a subset of {1, ..., m} W, finds the number of
gcolorings of {1, ...,m} that properly colors the
set A

Justin(g,m,a): the number of Proper colorings with g colors
of a set with a elements

JustinP(g,m,a): the probability
of Proper colorings with g colors
of a set with a elements
Homework for Monday April 25, 2011 class (due April 28, 2011)

Write a program, NuA(m,g,W,ListW):
that inputs pos. integers g and m,
a subset W, of {1, ..., m}, and a list of subsets of {1, ..., m},
ListW, and outputs the number of gcolorings of {1, ..., m} that
makes (i) W Properly Colored (ii) None of the sets in ListW Properly
by complete bruteforce.

By dividing by g^{m}, write the analogous program for
PrA(m,g,W,ListW), the probability that a random gcoloring
of {1, ..., m} would have the enough specifications.

Write a program RandCol(m,g) that inputs positive integers m and g,
and outputs, uniformly at random, one gcoloring of
{1, ...,m}, expressed as a list of m integers, each entry drawn from
{1, ..., g}

Write a program
AppxPrA(m,g,W,ListW,K), that approximates
PrA(m,g,W,ListW) by trying out, using RandCol(m,g) K times,
and finding those for which
(i) W Properly Colored (ii) None of the sets in ListW Properly
and dividing by K.

Experiment with various W's and ListW's (with at least three sets),
and see well AppxPrA(m,g,W,ListW,K) approximates PrA(m,g,W,ListW);

(Human mathematics):
Given two subsets A and B of {1, ...,m} such that
A intersect Complememt(B)=a, A intersect B=c,
Complement(A) intersect B=b,
find a closedform formula (in terms of a, b,c, and g) for the
probability that a (uniformlyat) random gcolring of {1, ..., m}
would make both A and B Properly Colored.

Read and understand the statements and proofs of Lemmas 3.6 and
3.7, pp. 89, in:
AlonBoppana masterpiece.

(Human mathematics, $5, to be divided)[corrected April 26, 2011, 12:32pm, thanks to CK LEE]:
Given three subsets A1 and A2, A3 of {1, ...,m} such that
(let C(S) be the complement of the set S)
A1 intersect A2 intersect A3=a111,
A1 intersect A2 intersect C(A3)=a110,
A1 intersect C(A2) intersect A3=a101,
A1 intersect C(A2) intersect C(A3)=a100
C(A1) intersect A2 intersect A3=a011,
C(A1) intersect A2 intersect C(A3)=a010,
C(A1) intersect C(A2) intersect A3=a001,
find a closedform formula
(in terms of a111, ..., a001, and g)
for the
probability that a (uniformlyat) random gcolring of {1, ..., m}
would make both A1, A2, and A3 Properly Colored.
Programs done on Thurs., April 28, 2011
Today we said goodbye to Boolean circuit complexity (but please go back to the
AlonBoppana masterpiece when you have a chance, read and reread it, it is worth the effort!),
and we followed the footsteps of my brilliant former PhD student
Thotsaporn "Aek" Thanatipanonda who wrote the following
masterpiece.
We started the following program,
chess.txt,
that contains procedures:

InBoard(pt,m,n): decides whether the point pt=[i,j] belongs to the m by n Chessboard

KingNeis(pt) : All the points reachable by the Chess King in one move

PathRook(pt1,pt2): all the points visited in the
rook's move from pt1 to pt

WMove(m,n,P): (not yet complete)
Inputs a position P (a triple [WK,WR,BK])
where WK are the coordinaes of the White King
BK are the coordinates of the Black King
WR are the coordinates of the White Rook
in an m by n chessboard [i,j], 1<=i<=m , 1<=j<=n
Homework for Thursday April 28, 2011 class (due May 2, 2011)

Finish up procedure WMove(m,n,P), that inputs pos. integers m and n and a position P=[WK,WR,BK] and outputs
the set of positions reachable from P on one move, if it is White's turn to move.

Write procedure BMove(m,n,P), that inputs pos. integers m and n and a position P=[WK,WR,BK] and outputs
the set of positions reachable from P on one move, if it is Black's turn to mov

Write a procedure IsCheckMate(m,n,P) that returns true if position P is a CheckMate for Black,
and false otherwise.
(Recall that the Black King is CheckMated if it is threatended by the White Rook, and has no safe place to go).

Write a procedure IsStaleMate(m,n,P) that returns true if position P is a Stalemate for Black
(it is not threatened by the White Rook, but wherever it goes it would die)
What We did on May 2, 2011
I thank Andrew Baxter for reminding me of the Experimental Mathematics'
class of 2009's
great group project. Today we planned (outside, while sipping
our coffees (5), teas(2), hot chocolate (1) lemonades(4) and water(1),
and sharing 5 healthy (oatmeal raisin) and 5 junky (chocolatechip)
cookies) the classproject for this year's class:
design and write a similar computergenerated webbook
for Rectangular (m by n) Chess endgame problems
(White to mate in k moves). The tentative deadline is
June 3, 2011.
Here is the organizational chart:
Big bosses: Dr. Emilie Hogan and Dr. Andrew Baxter

Chess Moves Generation Team: David John Wilson (leader),
Susan Durst, Simao Herdade, and Matthew Samuel .

Graphic Design Team: Andrew Baxter (leader),
Justin Gilmer, Jocelyn Quaintance, Emily Sergel .

Puzzle Solving/Designing Team: Brian Nakamura (leader),
Jacob Baron, Taylor Burmeister, CK Lee, Tim Naumovitz, Matthew Russel .
Homework for Monday May 2, 2011
No homework, but a first, preliminary draft of the
project
is due May 10, 2011.
Added May 16, 2011:
Here are the students'
evaluations.
Added June 9, 2011:
Here is the class's
awsome group project to generate minichess endgame puzzles.
Dr. Z.'s teaching page