Universal cycles and de Bruijn sequences
A universal cycle for a set S is a cyclic sequence u1u2 … u|S| where each substring of length n corresponds to a unique object in S. As an example, the cyclic sequence in the figure is a universal cycle (de Bruijn sequence) for the set of length 6 binary strings, where the 64 unique length 6 binary strings appear exactly once as a substring when the sequence is considered cyclicly.
Our goal is to study the existence of universal cycle for combinatorial objects, and efficiently construct one if such cycle exists.
- Efficient universal cycle constructions for weak orders. Joe Sawada and Dennis Wong. Discrete Mathematics, To appear.
- Greedy universal cycle constructions for weak orders. Marsden Jacques and Dennis Wong. In Proceedings of the 6th Annual International Conference on Algorithms and Discrete Applied Mathematics, 2020.
- A successor rule framework for constructing k-ary de Bruijn sequences and universal cycles. Daniel Gabric, Joe Sawada, Aaron Williams and Dennis Wong. IEEE Transactions on Information Theory, 2019.
- A framework for constructing de Bruijn sequences via simple successor rules. Daniel Gabric, Joe Sawada, Aaron Williams and Dennis Wong. Discrete Mathematics 341, 2018.
- A simple greedy de Bruijn sequence construction. XiaoFang Wang, Dennis Wong and WeiGuo Zhang. Sequences and Their Applications (SETA), 2018.
- Constructing de Bruijn sequences with co-lexicographic order: The k-ary grandmama sequence. Patrick Dragon, Oscar Hernandez, Joe Sawada, Aaron Williams and Dennis Wong. European Journal of Combinatorics 72, 2018.
- A new universal cycle for permutations. Dennis Wong. Graphs and Combinatorics 33, 2017.
- A simple shift rule for k-ary de Bruijn sequences. Joe Sawada, Aaron Williams and Dennis Wong. Discrete Mathematics 340, 2017.
- Generalizing the classic greedy and necklace constructions of de Bruijn sequences. Joe Sawada, Aaron Williams and Dennis Wong. Electronic Journal of Combinatorics 23, 2016.
- A surprisingly simple de Bruijn sequence construction. Joe Sawada, Aaron Williams and Dennis Wong. Discrete Mathematics 339, 2016.
- The lexicographically smallest universal cycle for binary strings with minimum specified weight. Joe Sawada, Aaron Williams and Dennis Wong. Journal of Discrete Algorithms on StringMasters, 28(0):31-40, 2014. StringMasters 2012 & 2013 Special Issue (Volume 1), 2014.
- Universal cycles for weight-range binary strings. Joe Sawada, Aaron Williams and Dennis Wong. In proceeding of 24th International Workshop on Combinatorial Algorithms (IWOCA 2013), LNCS 8288, pages 388-401, 2013.
- Novel universal cycle constructions for a variety of combinatorial objects. Dennis Wong. Ph.D. thesis, School of Computing Science, University of Guelph, 2015.
A Gray code for a set S is a listing s1, s2 ,…, s|S| of the elements of S such that consecutive strings in the listing differ by a small amount of changes. As an example, the listing in the figure is a Gray code for the set of length 4 binary strings where consecutive strings differ by exactly one bit. A universal cycle can also be considered as a Gray code, where consecutive strings differ by a single shift and also at most one bit change.
Our goal is to study the existence of Gray codes and devise efficient algorithms to generate Gray codes for various combinatorial objects.
- Generating Gray codes for weak orders in constant amortized time. Marsden Jacques, Dennis Wong and Kyounga Woo. Discrete Mathematics, To appear.
- Necklaces and Lyndon words in colexicographic and binary reflected Gray code order. Joe Sawada, Aaron Williams and Dennis Wong. Journal of Discrete Algorithms 46-47, 2017.
- Snakes, coils, and single-track circuit codes with spread k. Simon Hood, Daniel Recoskie, Joe Sawada and Dennis Wong. Journal of Combinatorial Optimization, 2013.
- Exhaustive search for maximal length coil-in-the-box codes. Joe Sawada and Dennis Wong. Technical Report, Department of Computing and Information Science, University of Guelph, 2008.
- A fast algorithm to generate Beckett-Gray codes. Joe Sawada and Dennis Wong. Electronic Notes in Discrete Mathematics (EuroComb 2007) 29, 571-577, 2007.
- Fast algorithm to generate Beckett-Gray codes and coil-in-the-box codes. Dennis Wong. M.Sc. thesis, Department of Computing and Information Science, University of Guelph, 2007.
Negative cycle detection
We study the problem of ﬁnding a negative weighted cycle in a directed weighted graph. As an example, the directed weighted graph on the right has a negative cycle (a) -> (b) -> (c) with weight equal to 5+(-20)+10 = -5.
Our research studies the properties of negative cycles in directed weighted graphs and improves the runtime of a wide range of commonly used algorithms in this area.
- Negative cycle detection problem. Henry Tam and Dennis Wong (supervised by Evangeline Young). In proceedings of 13th Annual European Symposium on Algorithms (ESA 2005), pages 652−663, 2005.
- Negative cycle cost detection problem. Henry Tam and Dennis Wong. B.Sc. FYP report, Department of Computer Science, The Chinese University of Hong Kong, 2005.
- Educational STEM Laboratory – An Experimental Paradigm, Theory Design and User Experience Case Study. Peter Yau, Dennis Wong and HongYing Qiu. In Proceedings of the 6th International Conference on Education and Training Technologies (ICETT), 2020.
- Continuous Education through Building a Work-and-Learn Relationship: How does the Industrial Attachment Program work in Hong Kong. Peter Yau, Dennis Wong and Andrew Lam. In Proceedings of the 3rd International Conference on Education Research and Policy (ICERP), 2020.
- Practicing Mobile-Commerce Like a Pro – Implementation of an education-oriented commercial trading system. Peter Yau, Hok Luen Woo, Joseph Leung and Dennis Wong. In Proceedings of the 6th International Conference on E-business and Mobile Commerce (ICEMC), 2020.
- Unmanned Shop Laboratory: An extensible and scalable research, teaching and learning smart space system. Peter Yau, Hok Luen Woo, Dennis Wong and Joe Wai Kin Kan. In Proceedings of the 3rd IEEE International Conference on Electronics Technology (ICET), 2020.
- Understanding Consumer Behavior by Big Data Visualization in the Smart Space Laboratory. Peter Yau, Hok Luen Woo, Ming Sum Lam and Dennis Wong. In Proceedings of the 5th International Conference on Big Data and Computing (ICBDC), 2020.
- SNudge: A Slidebar Nudge for users to practice better habits for mobile fingerprint authentication. Joon Han and Dennis Wong. In Proceedings of the 24th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2019), 2019.
- Flash, Buzz, Zap and Ouch! The sounds and sights of the Internet of Things in the classroom. Michael Rogers, Aziz Fellah and Dennis Wong. Journal of Computing Sciences in Colleges 32(5), 132−140, 2017.