Monday October 11 4:00 - 5:00 PM Kelley 1001
Paul Cull Professor Emeritus School of EECS Oregon State University A Tale of Two Puzzles Once upon a time, there were two puzzles. One was the Towers of Hanoi invented or introduced by Eduardo Lucas in 1883. The other was Spin-Out patented by William Keister in 1972. There are many stories about these puzzles. Some of these stories hint or claim that these puzzles have an intimate relationship with the Gray codes invented by Frank Gray in 1947. Here, we wish to show how these puzzles can be generalized and crossed to give give puzzles for every base and for every number of pieces. The Gray relationship will become clearer when we describe the graphs associated with the puzzles and the graph labelings induced by the puzzles. These labelings will have the Gray property in the appropriate base. Counter to claims that Gray counting is needed to solve these puzzles, we describe counting algorithms which solve these puzzles using a standard binary counter. We also give recursive and iterative algorithms for these puzzles. Biography Paul Cull is a founding member of the Computer Science Department at OSU. He came to OSU in 1970, and became Professor Emeritus of Computer Science in 2003. Dr. Cull has taught the full panoply of courses from computer organization to algorithms and theory of computation. This term he is offering the undergraduate course in algorithms. He is Theory Editor for Computing Reviews and a member of the Editorial Board of Scientiae Mathematicae Japonicae. Paul Cull's research interests are mathematical biology, theory of computation, and analysis of algorithms. His early work was on inferring gene linkage from pedigree data. Dr. Cull earned his Ph.D. at the University of Chicago, where he studied with the committees on mathematical biology and information science. He wrote his thesis on the analysis of neural nets. Over the years, Dr. Cull has worked on a large variety of topics and published papers in many venues. His most recent papers are in machine learning, neural nets, interco nnection networks, biological string alignment, discrete iterations, and error-correcting codes. He is the co-author of the book "Difference Equations: from rabbits to chaos" published by Springer in 2006. Dr. Cull started the Research Experience for Undergraduates (REU) program with the Mathematics Department in 1987, and continues working with REU students each summer. The results in this talk were developed with these (very special) summer students. _______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
