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