Official name: `642:587 Selected Topics in Discrete Math (Algorithmic Discrete Math)'.
Last Update: April 27, 2005.
TEXT: Handouts.
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
SORT1 Look also at Lara Pudwell's HEAP
Jan. 31, 2005: (Maximun Matching using the Alternating Path Algorithm) HALL
Look also at Paul Raff's Matching program, Ben Chen's Matching program, Leigh Cobbs's Stable Matching program, and Padmini Mukkamala's Stable Matchings and Heapsort programs,
Feb. 7, 2005: GuessRat, and GarsiaMilne, Garsia and Milne's Involution Principle:
Feb. 7, 2005: (Aleternating Paths throught the Combinatorics Curriculum)
Look also at Lara Pudwell's edgecolors.txt, a Maple implementation of an algorithm (due to Konig, 1916) to edge-color a bipartite graph and Leigh Cobbs's implementation of the Garsia and Milne Involution Principle.
See also the versions with nice graphics NKSvv by Vince Vatter, (coming up, this is just NKS) and NKScr, by Chris Ross.
Homework Due Feb. 28, 2005: modify it for 2D-random walk for
an A by B rectangle. In other words, write a program that
inputs integers A and B and outputs a list of lists, let's
call it L, such that L[i][j] is the expected life of
a fair-random walker (i.e. prob. 1/4 each for going
up, down, left, or right),
in the discrete rectangle
0<=x<=A, 0<=y<=B, currently at location (i,j), and
such that the walker dies when he (or she, or it) hits
one of the four fences : x=0,x=A,y=0,y=B.
Let's call this quantity F(A,B;i,j);
Then use my Maple package
GuessHolo to conejcture either a rational-function, or
a recurrence satisfied by F(A,A;1,1), and if possible
more generally.
Added Feb. 28, 2005: Many people did a good job,
in particular look at
Padmini Mukkamal's 2D-gambler program.
See also the nice program by Philip Matchett's, and Padmini Mukkamal's elegant human solution, and Ben Chen's Hanoi program, as well as Lara Pudwell's Hanoi program
See also Tin Bian's program .
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.