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:00noon-1:20pm)
• "Textbooks": classical articles,
  • The monotone circuit complexity of Boolean functions by Noga Alon and R.B. Boppana
  • Bounds for sorting by prefix reversal by Bill Gates and Christos Papadimitriou.
    See also a (18/11)n upper-bound and Colvey Roney-Dougal and Vince Vatter's awsome article
  • A 2.5n-lower bound on the combinatorial complexity of boolean functions by W.J. Paul .
  • The complexity of finite functions by Ravi Boppana and Michael Sipser.
  • More to TBA

• Dr. Zeilberger's Office: Hill Center 704 (732 445 2390 Ext. 1326)
• Dr. Zeilberger's E-mail: zeilberg at math dot rutgers dot edu (you MUST have MathIsFun in the message, or ExpMathRocks)
• Dr. Zeilberger's Office Hours: MTh 10:30am-11:30am and by appointment

Description

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 computer-generated and computer-assisted 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

• 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

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 Sheng-Lan 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)

1. (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]
2. 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.
3. Write a program that inputs an "explicit" (i.e. one given by an expression) C² 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.
4. (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 .)
5. (For everyone). Read and understand the wikipedia entry on Boolean Logic

Programs done on Monday, Jan. 24, 2011

• 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 #i-GENUINE 2-variable Boolean function
• An example of a straight-line 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 n-vectors of t's and f's

Homework for Monday, Jan. 24, class (due Jan. 27, 2011)

1. (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]
2. (For novices only) The current procedure nCube(n) outputs the set of vertices of the n-dimensional cube, {t,f}^n. Write a more general program nCubeG(n,S) that inputs a two-element set S and outputs the set (with 2ⁿ 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);
3. (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|ⁿ 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);
4. (For experts, optional challenge for novices) Write a program BF(n,SLP) that inputs a positive integer n and a straight-line 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 one-to-one correspondence between Boolean functions on n variables and subsets of the n-dimensional discrete unit cube:
   f-> {v; v in nCube(n), f(v)=true} ).

Programs done on Thursday Jan. 27, 2011

• BF(n,SLP): inputs a straight-line 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 n-vectors 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)

1. (For novices only) Read and do all the examples, plus make up similar ones, in pages 60-90 of Frank Garvan's awesome Maple booklet. [Hand in a printout of two pages with sample commands]
2. (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).
3. (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.
4. (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

• RandTriple(n): a random 3-element 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)

1. (For novices only) Read and do all the examples, plus make up similar ones, in pages 90-120 of Frank Garvan's awesome Maple booklet. [Hand in a printout of two pages with sample commands]
2. (For everyone) Read and understand the first two pages of Uri Zwick's article that I handed-in today.
3. (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).
4. (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]]
   
5. 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 3-CNFs (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.
6. 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

• BFtoDNF1(s): inputs a Boolean function with a single member given as the set of n-tuples 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 n-tuples 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)

1. [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 n-tuples of true-false.
2. [For everyone] Finish up procedure DNFtoSLP1(n,s). Right now it only handles sets s (i.e. clauses) with two elements.
3. [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)
4. [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

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

1. Write procedure DNFtoSLP(n,S), by iteratively "marrying" the SLPs generated by DNFtoSLP1(n,s) for the members s in S.
2. Write a program RandBF(n,K) that inputs positive integers n and K (between 0 and 2ⁿ) and outputs a random Boolean function on n variables, and K truth-points.
3. Read carefully pages 119-123 of Chapter 5 of Ingo Wegener's book that I handed-in today.
4. Read carefully the wikipedia entry on Quine-McCluskey algorithm
5. [Challenge for everyone!] Implement the Quine-McLuskey algorithm.
   Write a Maple program that inputs a Boolean function (as a set of n-vectors 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.
   1. 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 n-vectors 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!]
   2. [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

• 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 i-th component are the i-1 dimensional implicants (and hence having n-i+1 elements

Homework for Thursday, Feb. 10, 2011 class (due Feb. 14, 2011)

1. Some of you have already met the challenge of writing your own Quine-McLuskey 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 i-th item is the set of prime implicants of dimension i-1. (Hint, the last entry of Implicants(n,f) (that is non-empty) 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.
2. Write a program, QM(n,f) that inputs a pos. integer n and a Boolean function f, and outputs a (hopefully) optimal or near-optimal minimal DNF for it. (Hint: of course it is a subset of the set of prime implicants. If there are points (alias truth-vectors) that are only contained in ONE prime implicant, the corresponding prime-implicant 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.
3. 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ⁿ, and a positive integer i between 0 and n, and finds the average number of i-dimensional implicants (NOT prime implicants) amongsts all such Booean functions. Of course Implicants(n,a,0) should always be a.
4. ($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).
5. ($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 .

6. (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 Valentine-like shape.

Programs done on Monday, Feb. 14, 2011

Homework for Monday, Feb. 14, 2011 class (due Feb. 17, 2011)

1. 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 left-over points (not covered by these), and the left-over prime-implicants. Try to understand what is going on.
2. [Challenge] Think of a greedy algorithm that takes the left-over 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.
3. [Challenge] A Brute-force approach to the same problem, that guarantees optimality (alas at an exponential cost) is to examine all possible subsets of the set of left-over prime implicants (if there m prime implicants, there 2-1 possible non-empty sets. Find out which of these cover the left-over points, and amongsts those that do cover all these points, pick the "cheapest" one.
4. Check empirically as many as possible of the Amer. Math. Monthly problems I handed in today from the Feb. 2011 issue.
5. [up to $5 prize for EACH] Try to prove, using Maple, rigorously as many of these problems. If you cheat and use paper-and-pencil and/or human ingenuity, you may get a part of the $5.

Programs done on Thursday, Feb. 17, 2011

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

1. Using AND1(C1,C2,n) repeatedly write a procedure AND(L,n) that inputs a list of AND-clauses and outputs
   L[1] AND L[2] AND ... L[nops(L)]
2. write an adaptation of PIE(L), PIEdnf(n,S) that inputs a pos. integer n and a DNF S, expressed as a set of AND-clauses (each of which is a set of positive and negative integers, of course without any integer co-habiting with its negative) and outputs the NUMBER of truth-vectors (alias points in the n-dimen. unit cube) that belong to it divided by 2ⁿ. (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₁ is 1/2), in two literals is 1/4 etc.
3. Using PIEdnf(n,S) write a one-line program IsTaut(n,S) that inputs a pos. integer n and a DNF S and outputs true iff S is a tautology.
4. 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)
5. [$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

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

1. 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 2-clauses, like {1,-2}, and 1-clauses, 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}}.
2. Write a program TestPIEdnf(n,m,K) that inputs pos. integers n,m, and K, and generates, K times, a random 3-DNF, and runs PIEdnf on it. It should output the number of 3-DNF'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?
3. Modify PIEdnfF(L,n), call it PIEdnfF1(L,n), that also returns the i, i.e. stage in the Inclusion-Inclusion where we quitted for sure with either knowing that it is a tautology or not.
4. Write a program TestPIEdnfF1(n,m,K,x) that inputs pos. integers n,m, and K, and generates, K times, a random 3-DNF, and runs PIEdnfF on it, and outputs the number of 3-DNF'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 3-DNFs that exited at stage i of the PIE.
5. Shame on you for not reading carefully and understanding both two proofs demanded in the pop-quiz (about half of you were able to reproduce the first proof). Please read and understand pages 119-123 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!)
6. Read pp. 47-50 of the Bill Gates and Christos Papadimitriou masterpiece as well as the complete Colvey Roney-Dougal and Vince Vatter's awsome article

Programs done on Thursday, Feb. 24, 2011

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

1. Write a program Shells(n) that inputs a positive integer n and outputs a list whose i-th entry is the set of all permutations that can be reverse-prefix sorted with i steps (but not less). The union of all the entries of the output-list should be permute(n), and its nops (number of entries, i.e. its length) is the quantity f(n).
2. 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 prefix-sortable with i flips. See whether the sequences {Bill(n,1)}, {Bill(n,2)}, etc. are in Sloane.
3. ($5) prove the generating function, attributed by Sloane to Flajolet, for the number of adjancency-less permutations.
4. Read (and understand!) pp. 49-50 of the Bill Gates and Christos Papadimitriou masterpiece.
5. Program the sorting in Fig. 1.

Programs done on Monday, Feb. 28, 2011

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

1. 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 distances-squared 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 four-tuple of distances-squared. By plugging-in several spefic numeric values for a,b,x,y try and find the neccessary condition
2. (5$ to be divided) by using human (and/or computer) ingenuity, prove rigorously that necessary condition, and also prove that it is sufficient.
3. (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.
4. 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.
5. 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.
6. 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

• Flip(pi,i): flips the i-th 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 i-th 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 flip-places, 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)

1. 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.
2. Write a program aWLS1(pi,r) that inputs a permutation pi and outputs all the permutation that allow a wasteless sort until the r-th flip, then at the r-th 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).
3. 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.
4. 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 t-1), 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 non-existent (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

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

1. Modify NRP(a,b) and write a program CRP(a,b) (Clever Recursive product), using the deep identity
   ad+bc=(a+b)(c+d)-ac-bd
   
2. By using time();, experiment, with very large integers a and b, (generated randomly) whether CRP(a,b) is significantly faster than NRP(a,b).
3. (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)
4. (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

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

1. 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]]
2. Using BreakUp(pi) write a new version of WhatType(pi)
3. 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.
4. 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.
5. Have a nice and relaxing Spring Break!

Programs done on Monday, March 21, 2011

• FirstBlock(pi): inputs a permutation pi and outputs the first (consectutive) block (may be a singleton) written as a list, and the left-over. 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)

1. 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]].
2. Ditto for WhatType3(pi).
3. (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).
4. 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 (1-z)^(-a) by n^(a-1)*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 (1-z)^(-a)*(-log(1-z)/z)^b by n^(a-1)/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)

1. Write procedure Test3(n), testing Example 2 on page 564 of Philippe Flajolet's article on Singular Combinatorics
2. Write a procedure TestExample1(N) , testing Example 1 on page 564 of Philippe Flajolet's article on Singular Combinatorics
3. 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))
4. (Challenge!) Guess the asymptotic behavior a(n)=Caⁿn^β of the sequence Shark(N,3), and Shark(N,4), except for the C.
5. (Big Challenge!) Guess the asymptotic behavior a(n)=C*aⁿn^β of the sequence Shark(N,k), including the C! Prove it!
6. Fix procedure s(z,N).
7. (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

• 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

Homework for Monday March 28, 2011 class (due March 31, 2011)

1. 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 padded-version of a a type PD(T) to be the same with 0-s 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).
2. 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.
3. 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

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

1. Finish up BFTF by first finishing up SphereT, writing BallT (the type analog of Ball), and whatever it takes.
2. [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.
3. (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 computer-generated, 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

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 i-th 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 Gates-Papadimitriou prefix-sorting algorithm.

Homework for Monday April 4, 2011 class (due April 7, 2011)

1. Code the first formula in Jesús Guillera's amazing homepage. Try to get as many digits of Pi as possible.
2. Code the second (still conjectured) formula in Jesús Guillera's amazing homepage. Try to get as many digits of Pi as possible.
3. 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]

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

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

1. 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 Jones-Pevzner book on informatics.
2. 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.
3. Using the completed WhatTypeG(pi), and using the BFTF(pi) of Apr4.txt write a perfix-sorting 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 "meta-information" 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

• JB.txt,
• Apr4.txt,
• WTck.txt,

Homework for Monday April 11, 2011 class (due April 14, 2011)

1. 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 block-lengths 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.
2. 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.
3. (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.
4. Read (and understand!) the first four pages of the Noga Alon-Ravi Boppana masterpiece.

Programs done on Thurs., April 14, 2011

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

1. A MSLP (Monotone Straight Line Program) on n variables and m non-input 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^n-1 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).
2. Write a program ACtoMBF(AC) that inputs an antichain and outputs the corresponding monotone Boolean function
3. 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

We started to implement the constuctions and definitions in the Noga Alon-Ravi Boppana masterpiece. (Combinaorica 7(1) (1987) 1-22), 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)

1. 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]}}
2. Using Mchoose, write a new version of Clusure1 that does exactly what the Alon-Boppana article intends.

Programs done on Thursday, April 21, 2011

• Mchoose(S,k): inputs a set S and a pos. integer k and outputs the set of MULTI-SETS 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 so-called property P(r,k) in p. 5 of Alon-Boppana Combinatorica 7(1)(1987) 1-22
• 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)

1. Using gNCP(L), write a program ExtremePrk(r,k) that uses procedure gNCP(L) to constant the family of all possible menu-choices from a k-course meal, where each course has (r-1) different dishes to choose from, and all the dishes are distinct.
2. Check that ExtremePrk(r,k) has property P(r,k) for ALL 1 ≤ r ≤ 3 and 2 ≤ k ≤ 4
3. Read and understand the proof of Lemma 3.2 on p.6 of the Alon-Boppana masterpiece.
4. 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(r-1,k-|C|), by trying out various F.
5. (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

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

1. 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 g-colorings of {1, ..., m} that makes (i) W Properly Colored (ii) None of the sets in ListW Properly by complete brute-force.
2. By dividing by g^m, write the analogous program for PrA(m,g,W,ListW), the probability that a random g-coloring of {1, ..., m} would have the enough specifications.
3. Write a program RandCol(m,g) that inputs positive integers m and g, and outputs, uniformly at random, one g-coloring of {1, ...,m}, expressed as a list of m integers, each entry drawn from {1, ..., g}
4. 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.
5. 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);
6. (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 closed-form formula (in terms of a, b,c, and g) for the probability that a (uniformly-at-) random g-colring of {1, ..., m} would make both A and B Properly Colored.
7. Read and understand the statements and proofs of Lemmas 3.6 and 3.7, pp. 8-9, in: Alon-Boppana masterpiece.
8. (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 closed-form formula (in terms of a111, ..., a001, and g) for the probability that a (uniformly-at-) random g-colring of {1, ..., m} would make both A1, A2, and A3 Properly Colored.

Programs done on Thurs., April 28, 2011

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 chess-board [i,j], 1<=i<=m , 1<=j<=n

Homework for Thursday April 28, 2011 class (due May 2, 2011)

1. 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.
2. 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
3. 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).
4. 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 (chocolate-chip) cookies) the class-project for this year's class: design and write a similar computer-generated webbook for Rectangular (m by n) Chess end-game 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.