wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (04/13/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
REVISED ROOM CHANGE!
DATA STRUCTURES SEMINAR
-Monday, April 17, 1989
Mr. Ricardo Baeza-Yates will speak on "Searching Regular Expressions".
TIME: 3:30-5:30 PM
ROOM: DC 1302
ABSTRACT
We present algorithms for efficient searching of
regular expressions on preprocessed text. We obtain
logarithmic (in the size of the text) average time for
a wide subclass of regular expressions, and sublinear
average time for any regular expression, hence
providing the first known algorithm to achieve this
time complexity.
The motivation behind these algorithms is the work done
in the New Oxford English Dictionary Project.
As a subproduct of the analysis of one of the
algorithms, a technique to solve matricial recurrences
is proposed. This technique can be applied to other
problems, like fringe analysis and partial match
queries in k-d tries.
---wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (05/25/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURES SEMINAR
-Monday, May 29, 1989
Professor Mireille R`gnier, INRIA, France, will speak on
"An Algebraic Analysis of the Knuth-Morris-Pratt
Algorithm."
TIME: 3:30 p.m.
ROOM: DC 1304
ABSTRACT
We present an average analysis of a basic string-
searching algorithm: the Knuth-Morris-Pratt algorithm.
We consider the number of text-pattern comparisons
performed when searching a pattern p in a text t of
length n. It is known to be O(n). We show that for
a given pattern p and a random text t, this cost is
asymptotically c subscript p n. Averaging over all
possible patterns p yields a constant of linearity c.
When the cardinality q of the alphabet is large,
it is proven that
c approximates 1 + 1 over q . An algebraic scheme is
used, based on combinatorics on words and generating
functions. First, the problem is reduced to a problem
of word enumeration. Then, known results from
combinatorics of words apply, which allow the
computation of the associated generating functions.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (10/17/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURES SEMINAR
-Wednesday, October 18, 1989
Mr. Ron McFadyen, graduate student, Dept. of Computer
Science, will speak on ``Partial Match Retrieval When
Attributes Are Independently Specified.''
TIME: 10:30 a.m.
ROOM: DC 1331
ABSTRACT
We consider the cost of partial match queries in gray
code and standard binary hash files when the
probability of an attribute being specified is
independent of other attributes. Query cost is modelled
using cluster access and page transmissions. The cost
function developed yields properties concerning bit
assignments to attributes.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (01/18/90)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURES SEMINAR
-Wednesday, January 24, 1990
Darrell Raymond, Dept. of Computer Science, University
of Waterloo, will speak on ``lector: An Interactive
Formatter for Tagged Text.''
TIME: 1:30 p.m.
ROOM: DC 3307
ABSTRACT
lector is an X.11 program that provides provides
highly interactive text formatting. Unlike many
existing text previewers,lector accepts
descriptively marked-up text, permits multiple
views, and interacts well with other programs
(including other invocations of lector). Appropriate
selection of texts and styles enables lector to act
as text previewer, database browser, code
prettyprinter, or menu utility. lector's design
involves an interesting set of trade-offs in an
attempt to maximize efficiency, simplicity, and
generality, demonstrating the utility of isolating
text display in a single tool.
January 18, 1990