Dense and Cyclic Gray Codes
Guest Speaker: Dr. Thomas H. Cormen, Emeritus Professor, Dartmouth College
Moderated by Dr. Reza Rawassizadeh, Associate Professor of Computer Science
Abstract: The binary reflected Gray code, patented by Frank Gray in 1953, is a permutation of the sequence ⟨0, 1, …, n-1⟩, 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 exactly 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 ⟨0, 1, …, n-1⟩ with the Gray-code property for any integer n > 1? The answer turns out to be surprisingly simple, but not obvious at first why it should work. When can we create a dense Gray code with the cyclic Gray-code property, and how do we do it? The answer here is a bit more obvious—once you have already seen it.
Time-permitting, I will also touch on Gray codes for radices other than 2 and for mixed radices.
All results are joint work with my senior thesis students, Jessica Fan ’17 and Devina Kumar ’18.
Speaker Bio: Thomas H. Cormen is Emeritus 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. He focuses on algorithms and software infrastructure to mitigate the high latency inherent in accessing the outer levels of the memory hierarchy and in interprocessor communication. Lately, he has also been examining fundamental questions about Gray codes.