Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McMaster University

$19,000.00

String algorithms and their implementation, intelligent tutors

FY 2007-08

Summary
(1) Suffix data structures and related algorithms. The focus of the research is "relaxed" versions of suffix trees and arrays (i.e. without regards to lexicograhic ordering); their computation in linear time with hight memory efficiency, their transformation to "regular" suffix trees and arrays, their use for applications. The main objective is a fast linear non-recursive memory efficient algorithm for computing suffix trees and arrays. The research will explore the following path to such an algorithm: first compute a "relaxed" version of the data structure, then transform it to the "regular" structure. (2) The periodicity in strings. The investigation of mathematical and combinatorial properties of the function r(n) - the maximun number of runs (maximal non-extendible repetitions) over all strings of length n. The main objectives are: to prove that asymptoticaly r(n)<n, to find the structurual properties of strings with large number of runs, and to build a structural theory of periodicities. (3) C/C++ implementations of strings algorithms. This part of the proposal is concerned with building a library of robust and polymorphic string algorithms implemented in C/C++ usable for a variety of alphabets, with minimized memory use, and with parametric control of the size of working memory. (4) Intelligent tutoring systems. The main goal is a design of an intelligent tutoring system for ER modelling. The proposed architecture will allow problems and solutions to be generated rather than using a "canned" set of problems and solutions.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
25112-2006
Name nom
Franek, Frantisek
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2006
Award amount
19000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
2
Nb partie
5
Application title
String algorithms and their implementation, intelligent tutors
Keyword
NA
Application summary
(1) Suffix data structures and related algorithms. The focus of the research is "relaxed" versions of suffix trees and arrays (i.e. without regards to lexicograhic ordering); their computation in linear time with hight memory efficiency, their transformation to "regular" suffix trees and arrays, their use for applications. The main objective is a fast linear non-recursive memory efficient algorithm for computing suffix trees and arrays. The research will explore the following path to such an algorithm: first compute a "relaxed" version of the data structure, then transform it to the "regular" structure. (2) The periodicity in strings. The investigation of mathematical and combinatorial properties of the function r(n) - the maximun number of runs (maximal non-extendible repetitions) over all strings of length n. The main objectives are: to prove that asymptoticaly r(n)<n, to find the structurual properties of strings with large number of runs, and to build a structural theory of periodicities. (3) C/C++ implementations of strings algorithms. This part of the proposal is concerned with building a library of robust and polymorphic string algorithms implemented in C/C++ usable for a variety of alphabets, with minimized memory use, and with parametric control of the size of working memory. (4) Intelligent tutoring systems. The main goal is a design of an intelligent tutoring system for ER modelling. The proposed architecture will allow problems and solutions to be generated rather than using a "canned" set of problems and solutions.