Thoman Cormen

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.

Because Gray codes apply to non-binary integer representations as well, 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, D

Biography:

Bio:  Thomas H. Cormen is Emeritus Professor in the Dartmouth College Department of Computer Science, which he joined in 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.  Most of Professor Cormen's research pertained to algorithms and software infrastructure to mitigate the high latency inherent in accessing the outer levels of the memory hierarchy and in interprocessor communication.  Toward the end of his academic career, he examined fundamental questions about Gray codes. After retiring from Dartmouth in 2022, Professor Cormen joined the board of COVER Home Repair of White River Junction, Vermont. He was elected to the New Hampshire House of Representatives in 2022 from Ward 3 of the City of Lebanon and serves as deputy ranking member on the Science, Technology and Energy Committee.