Grant: Discovery Grants Program - Individual
University of Victoria
$30,000.00
Efficient algorithms for sequencing, counting, manipulating and visualizating discrete structures
EF 2011-12
Résumé
The purpose of this research is to investigate essential algorithmic and mathematical properties of certain fundamental discrete structures, including Venn/Euler diagrams, Gray codes, nested recurrence relations, and polynomials over finite fields. Of these structures, Venn/Euler diagrams will be most familiar to the general public. Formally, a Venn diagram consists of n simple closed curves drawn in the plane with the property that each of the 2^n intersections of the interiors or exteriors of the curves is non-empty and connected. If regions are allowed to be empty, then it is an Euler diagram. There is a demand for software that will render ""Venn"" diagrams of populations in such a way that the area of each region is in proportion to the size of the underlying population. Basic questions about when this is possible, and if possible, how to best draw the diagram from the users point of view, are still unresolved, although some progress has been made. One goal of this research is to resolve these questions.
Other problems that will be investigated first arose in Hofstadter's famous book: Godel, Escher and Bach; namely determining properties of the recurrence relation Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)), with Q(1) = Q(2) = 1, and a plethora of related similar recurrence relations. As an example problem, it is not known whether Q(n) is defined for all natural numbers n.
We will continue our work on discovering and efficiently implementing combinatorial Gray codes, which are lists of discrete objects in which successive objects are ""close"" in some natural sense.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
3379-2009
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
2011
Competition year année de concours
2009
Award amount
30000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
3
Nb partie
5
Application title
Efficient algorithms for sequencing, counting, manipulating and visualizating discrete structures
Keyword
NSERC
Application summary
The purpose of this research is to investigate essential algorithmic and mathematical properties of certain fundamental discrete structures, including Venn/Euler diagrams, Gray codes, nested recurrence relations, and polynomials over finite fields. Of these structures, Venn/Euler diagrams will be most familiar to the general public. Formally, a Venn diagram consists of n simple closed curves drawn in the plane with the property that each of the 2^n intersections of the interiors or exteriors of the curves is non-empty and connected. If regions are allowed to be empty, then it is an Euler diagram. There is a demand for software that will render ""Venn"" diagrams of populations in such a way that the area of each region is in proportion to the size of the underlying population. Basic questions about when this is possible, and if possible, how to best draw the diagram from the users point of view, are still unresolved, although some progress has been made. One goal of this research is to resolve these questions.
Other problems that will be investigated first arose in Hofstadter's famous book: Godel, Escher and Bach; namely determining properties of the recurrence relation Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)), with Q(1) = Q(2) = 1, and a plethora of related similar recurrence relations. As an example problem, it is not known whether Q(n) is defined for all natural numbers n.
We will continue our work on discovering and efficiently implementing combinatorial Gray codes, which are lists of discrete objects in which successive objects are ""close"" in some natural sense.