wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (04/19/89)
Approximate String Matching".
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
-Monday, April 24, 1989
Mr. Esko Ukonnen of University of Helsinki will speak
on "Efficient Approximate String Matching".
TIME: 3:30 PM
ROOM: DC 1302
ABSTRACT
We discuss recent advances in sequential algorithms for
computing the edit distance between two strings and for
finding approximate occurrences of a string (the
pattern) in another string (the text). Such algorithms
can be based on a very simple dynamic programming
method with running time O(mn) where m and n are the
lengths of the two strings compared. The emphasis of
the talk is on different ideas of speeding up the basic
dynamic programming. The resulting algorithms include a
method for the edit distance problem with the desirable
property of being the faster the smaller is the actual
distance. For the approximate string pattern matching
problem we obtain various O(kn) methods where n is the
length of the text and k is the maximum distance
allowed in a match.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (07/06/89)
will speak on ``Priority Search Trees: Applications and Variations.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
-Monday, July 10, 1989
Professor Dr. Thomas Ottman, University of Freiburg, will speak
on "Priority Search Trees: Applications and
Variations."
TIME: 3:30 p.m.
ROOM: DC 1302
ABSTRACT
Priority search trees, invented by McCreight, combine
properties of search trees and heaps. They were
originally used as a data structure in a time and space
optimal algorithm for reporting all pairs of
intersecting rectangles in a given set of iso-oriented
rectangles in the plane. Possible applications,
however, go beyond this special problem. We discuss the
dynamic fixed windowing problem as an example. Here
insertions and deletions of points are possible and
range queries with a translated polygonal window of
fixed size.
Variants of priority search trees are obtained by
choosing an appropriate coordinate system, an
underlying class of leaf search trees, the number of
points to be stored per node, and the memory (internal
or external). We discuss several of these variants, in
particular the difficulties in designing appropriate
external versions. It turns out that a new class of
red-black trees is useful in this context.