Math 587: Algorithmic Discrete Math Spring 2005 (Rutgers University) Webpage

Official name: `642:587 Selected Topics in Discrete Math (Algorithmic Discrete Math)'.

Last Update: April 27, 2005.

TEXT: Handouts.


Many proofs in Discrete Math are really algorithms in disguise. We will cover selected topics in discrete math from an algorithmic viewpoint, using Maple.

The format will follow the succesful format of Spring 2003 Math 583 : one class per week, traditional, and one class per week: in the computer lab. No former knowledge of Maple is needed. People with little or no Maple background will be tutured.

People who take this class will have a very good chance of getting a publication

Programs done in Class and by Students

Probelm sets

Untaken Projects

Taken Projects

  • Leigh Cobbs: Study the Complexity of the Involution Principle, possibly using ideas from Symbolic Moment Calculus I., and All the Moments of the Vertex Degrees).
  • Steve Curran: Study generalized but simplified Chess (on an m by n board), at the very least solving end-game problems with one White King, one White Rook, and one Black King, like in the first chapter of Capablanca's book "Fundamentals of Chess". First find the optimal strategy for small m and n (by the all-purpose alpha-beta algorithm), then detect some patterns (probaby recursive), and then formulate an optimal strategy for general m and n.

    Posted April 27, 2005: Steve's code and the Win32 executable are posted at Steve Curran's website.  To compile it on Unix/Linux, download the source to your directory and run "gcc *.cpp -o Chess" then run the program with "./Chess".  There's a sample run on the site as well in case the interface is a little confusing.

  • Ben Chen and Tin Bian: Generalized Tower of Hanoi
  • Ben Chen, Phlip Matchett Paul Raff: Prove Fibonacci Identities Bijectively, using my translation method
  • Yi Jin' Fast algorithms for monomial symmetric functions. Download Yi Jin's project.
  • Mohamud Mohammed: q-Hypergeometric Discovery
  • Padmini Mukkamal: Tree bijections.
  • Chris Ross: Study in much greater depth, and in k-dimensions Gambler's ruin (see Feb. 21, 2005 class above), and its many extensions and variations, using GuessHolo.
  • Eric Rowland: Investigate analogs/generalizations of Mehler's formula (using ideas from Foata's proof) for generalized-Hermite polynomials, whose generating function is sum(H_n(x,a,b,c)t^n/n!)=exp(a*t+b*t^2/2+c*t^3/3!)
  • Thotsaporn Thanatipanonda (Aek): Studying the Haiman (ex-) conjecture from a Grober point of view.