{"id":26307,"date":"2022-02-11T07:34:28","date_gmt":"2022-02-11T12:34:28","guid":{"rendered":"http:\/\/www.bu.edu\/csmet\/?p=26307"},"modified":"2024-06-21T11:49:04","modified_gmt":"2024-06-21T15:49:04","slug":"dense-and-cyclic-gray-codes","status":"publish","type":"post","link":"https:\/\/www.bu.edu\/csmet\/2022\/02\/11\/dense-and-cyclic-gray-codes\/","title":{"rendered":"Dense and Cyclic Gray Codes"},"content":{"rendered":"<p><iframe loading=\"lazy\" width=\"400\" height=\"285\" style=\"padding: 25px;\" align=\"left\" src=\"https:\/\/cdnapisec.kaltura.com\/p\/2159741\/embedPlaykitJs\/uiconf_id\/54272102?iframeembed=true&#038;entry_id=1_883zbed8\" width=\"400\" height=\"285\" allowfullscreen webkitallowfullscreen mozAllowFullScreen allow=\"autoplay *; fullscreen *; encrypted-media *\" sandbox=\"allow-forms allow-same-origin allow-scripts allow-top-navigation allow-pointer-lock allow-popups allow-modals allow-orientation-lock allow-popups-to-escape-sandbox allow-presentation allow-top-navigation-by-user-activation\" frameborder=\"0\" title=\"Kaltura Player\"><\/iframe><\/p>\n<p><strong>Guest Speaker: <\/strong><a href=\"https:\/\/faculty-directory.dartmouth.edu\/thomas-h-cormen\">Dr. Thomas H. Cormen<\/a>, Emeritus Professor, Dartmouth College<br \/>\n<em>Moderated by <a href=\"https:\/\/www.bu.edu\/csmet\/profile\/reza-rawassizadeh\/\">Dr. Reza Rawassizadeh<\/a>, Associate Professor of Computer Science<\/em><\/p>\n<p><strong>Abstract:<\/strong> The binary reflected Gray code, patented by Frank Gray in 1953, is a permutation of the sequence \u27e80, 1, \u2026, n-1\u27e9, 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.<\/p>\n<p>What if n is not a power of 2? How can we create a dense Gray code: a permutation of \u27e80, 1, \u2026, n-1\u27e9 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\u2014once you have already seen it.<\/p>\n<p>Time-permitting, I will also touch on Gray codes for radices other than 2 and for mixed radices.<\/p>\n<p>All results are joint work with my senior thesis students, Jessica Fan \u201917 and Devina Kumar \u201918.<\/p>\n<p><strong>Speaker Bio:<\/strong> 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&#8217;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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 \u27e80, 1, \u2026, n-1\u27e9, where n is a power of 2, with the property that the binary [&hellip;]<\/p>\n","protected":false},"author":2828,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10840],"tags":[],"_links":{"self":[{"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/posts\/26307"}],"collection":[{"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/users\/2828"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/comments?post=26307"}],"version-history":[{"count":4,"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/posts\/26307\/revisions"}],"predecessor-version":[{"id":29212,"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/posts\/26307\/revisions\/29212"}],"wp:attachment":[{"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/media?parent=26307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/categories?post=26307"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.bu.edu\/csmet\/wp-json\/wp\/v2\/tags?post=26307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}