img img img img

Thomas H. Cormen

Dense and Cyclic Gray Codes for Binary, Fixed, and Mixed Radices

The binary reflected Gray code, patented by Frank Gray in 1953, is a permutation of the sequence $ \langle 0, 1, \ldots, n-1 \rangle $, where $n$ is a power of ~$2$, with the property that the binary representation of each number in the sequence differs from that of the preceding number in only one bit. The binary reflected Gray code is also cyclic, in that the last and first numbers also differ in only one bit.

What if $n$ is not a power of ~$2$? How can we create a dense Gray code: a permutation of $\langle 0, 1, \ldots, n-1 \rangle$ with the Gray-code property for any integer $n > 1$? When can we crate a dense Gray code with the cyclic Gray-code property, and how do we do it? How about for radices other than~$2$? Or for mixed radices? In this talk, I will show you how and when we can create dense and cyclic Gray codes for binary, fixed, and mixed radices, along with some applications of binary Gray codes.

All results are joint work with my senior thesis student, Jessica Fan.

Thomas H. Cormen

Thomas H. Cormen is a Professor in the Dartmouth College Department of Computer Science, where he has been since 1992. He served as the department chair from 2009 to 2015, and he directed the Dartmouth Institute for Writing and Rhetoric from 2004 to 2008. Professor Cormen received the B.S.E. degree in Electrical Engineering and Computer Science from Princeton University in 1978 and the S.M. and Ph.D. degrees in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 1986 and 1992, respectively. An ACM Distinguished Educator, he is coauthor of the leading textbook on computer algorithms, Introduction to Algorithms, which he wrote with Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. He is also the author of Algorithms Unlocked. Professor Cormen's primary research interests are in algorithm engineering and parallel computing.