Grant: Discovery Grants Program - Individual
University of Victoria
$39,000.00
Research in Combinatorial Algorithms
FY 2016-17
Summary
Combinatorial algorithms are a core foundational area of computer science. The area is focused on algorithms that operate on finite structures, particularly those that have precise mathematical descriptions. The objective of this research is to identify some problems and structures that are fundamental, find clever ways to solve the problems algorithmically, write code to implement them efficiently, and analyze them mathematically. Also, my grad students and I are not afraid to pursue in considerable detail some side-angle problem that arises in these steps, if such problem seems somehow intellectually interesting and challenging. This proposal focuses on five areas: Gray codes and de Bruijn cycles, nested recurrence relations, Venn diagrams, tatami tilings, and bobbin lace.
Gray codes and de Bruijn Cycles:
Search spaces are often highly-structured and huge; we intend to continue our development of efficient algorithms for searching, exhaustively and otherwise, in these spaces. Of primary interest are combinatorial Gray codes, which are exhaustive lists in which successive combinatorial objects differ by only a constant amount. Such Gray codes are a necessary precursor to the most efficient of all generation algorithms, those in which only a constant amount of work is done between successive objects generated. Gray codes and de Bruijn cycles have many applications, including computational biology, position detection on rotating axles, combination lock breaking, etc.
Nested recurrence relations:
Recurrence relations are a fundamental tool of computer science and mathematics. In recent years, we have begun trying to better understand ""nested recurrence relations"" (NRRs), which have received scant attention in the past as compared with the traditional non-nested recurrence relations. The prototypical NRR is Hofstadter's recurrence: Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)), popularized in the Pulitzer Prize winning book ""Godel, Escher, Bach: An Eternal Golden Braid"". The key syntactic features of this recurrence are that it only uses addition, subtraction, and composition --- and the depth of nesting of the composition is at least two. The recurrences we intend to study all have these key features. We will classify them according to whether they are decidable or not, and provide combinatorial bijections for them whenever possible.
Venn and Euler Diagrams
Most people are familiar with small ""Venn"" diagrams, and their use in conveying set relationships and explaining syllogisms. Our research is focused on finding symmetric Venn diagrams, both in the plane and also on the sphere, and on exhaustive listing of diagrams with a small number of curves.
Bobbin Lace:
Bobbin lace is an old art form, dating back to at least the 16th century, for making fine lace fabric patterns. Given the regular and often symmetric qualities of these patterns, amazingly, there seems to never have been an attempt to precisely catalog and understand the possible patterns, although some ad hoc observational listing and classification has been done. Our aim is to provide a firm mathematical and computational base for bobbin lace patterns.
Tatami Tilings:
A tiling of an orthogonal region with rectangles is said to be tatami if no four rectangles meet. Such a restriction has a long history in the arrangement of tatami mats on the floors of Japanese rooms. Previous to my work in this area, there were only a couple of mentions of them in puzzle books and in architectural journals. This is somewhat surprising, since the tatami constraint is perhaps the most natural local constraint to place on a tiling. We will continue our investigations into the properties of these tilings and their generalizations.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-04883
Name nom
Ruskey, Frank
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
39000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Partie
3
Nb partie
5
Application title
Research in Combinatorial Algorithms
Keyword
NSERC
Application summary
Combinatorial algorithms are a core foundational area of computer science. The area is focused on algorithms that operate on finite structures, particularly those that have precise mathematical descriptions. The objective of this research is to identify some problems and structures that are fundamental, find clever ways to solve the problems algorithmically, write code to implement them efficiently, and analyze them mathematically. Also, my grad students and I are not afraid to pursue in considerable detail some side-angle problem that arises in these steps, if such problem seems somehow intellectually interesting and challenging. This proposal focuses on five areas: Gray codes and de Bruijn cycles, nested recurrence relations, Venn diagrams, tatami tilings, and bobbin lace.
Gray codes and de Bruijn Cycles:
Search spaces are often highly-structured and huge; we intend to continue our development of efficient algorithms for searching, exhaustively and otherwise, in these spaces. Of primary interest are combinatorial Gray codes, which are exhaustive lists in which successive combinatorial objects differ by only a constant amount. Such Gray codes are a necessary precursor to the most efficient of all generation algorithms, those in which only a constant amount of work is done between successive objects generated. Gray codes and de Bruijn cycles have many applications, including computational biology, position detection on rotating axles, combination lock breaking, etc.
Nested recurrence relations:
Recurrence relations are a fundamental tool of computer science and mathematics. In recent years, we have begun trying to better understand ""nested recurrence relations"" (NRRs), which have received scant attention in the past as compared with the traditional non-nested recurrence relations. The prototypical NRR is Hofstadter's recurrence: Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)), popularized in the Pulitzer Prize winning book ""Godel, Escher, Bach: An Eternal Golden Braid"". The key syntactic features of this recurrence are that it only uses addition, subtraction, and composition --- and the depth of nesting of the composition is at least two. The recurrences we intend to study all have these key features. We will classify them according to whether they are decidable or not, and provide combinatorial bijections for them whenever possible.
Venn and Euler Diagrams
Most people are familiar with small ""Venn"" diagrams, and their use in conveying set relationships and explaining syllogisms. Our research is focused on finding symmetric Venn diagrams, both in the plane and also on the sphere, and on exhaustive listing of diagrams with a small number of curves.
Bobbin Lace:
Bobbin lace is an old art form, dating back to at least the 16th century, for making fine lace fabric patterns. Given the regular and often symmetric qualities of these patterns, amazingly, there seems to never have been an attempt to precisely catalog and understand the possible patterns, although some ad hoc observational listing and classification has been done. Our aim is to provide a firm mathematical and computational base for bobbin lace patterns.
Tatami Tilings:
A tiling of an orthogonal region with rectangles is said to be tatami if no four rectangles meet. Such a restriction has a long history in the arrangement of tatami mats on the floors of Japanese rooms. Previous to my work in this area, there were only a couple of mentions of them in puzzle books and in architectural journals. This is somewhat surprising, since the tatami constraint is perhaps the most natural local constraint to place on a tiling. We will continue our investigations into the properties of these tilings and their generalizations.