wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (06/15/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Monday, June 19, 1989
Denise M. Woit, graduate student, Dept. of Computer
Science, University of Waterloo, will speak on
"Rational Testing for Computational Geometry Codes: A
Case Study
TIME: 2:30 p.m.
ROOM: DC 3540
ABSTRACT
As the role of software grows in our society, the need
for reliable and practical software testing techniques
increases. Functional testing is one method that may
help fulfill this need. While many functional testing
techniques have been theorized, they are often too
involved or too complicated to be of practical use.
As well as the general testing technique, the testing
process must also be of practical use: the testing
environment should be engineered so that the tests will
execute with minimal human interaction and be easily
repeatable.
In the area of computational geometry, algorithms are
sometimes found to be intricate and counter-intuitive;
these algorithms, especially, are in need of software
testing techniques which are reliable, yet practical.
One such algorithm is that of the visibility polygon
problem.
The fundamentals of a visibility polygon algorithm,
VISPOL, are presented; a functional testing technique
and environment are proposed which, while specific to
VISPOL, can be extended into a general methodology for
the testing of computational geometry codes; an account
of the design and implementation of the VISPOL
algorithm, using current software engineering
practices, is given; and, the results of the proposed
testing technique and environment applied to the VISPOL
implementation are presented and analyzed.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (07/28/89)
Dept. of Computer Science, will speak on
``Performance Studies in Optical Disk Storage.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Thursday, August 3, 1989
Mr. K. Hatzilemonias, graduate student, Dept. of
Computer Science, will speak on ``Performance Studies
in Optical Disk Storage.''
TIME: 1:00 p.m.
ROOM: DC 1302
ABSTRACT
Optical disks, due to the low storage cost per bit of
stored information, easy replication, large storage
capacity, and long archival life, are projected to be
the dominant storage technology for many storage
intensive applications.
In the research presented we investigate the various
types of available optical disk storage systems and
through experimentation we identify their performance
characteristics.
Based on the experimental results, mathematical models
capturing the behavior of these systems have been
developed and validated against the actual systems they
represent. These models are incorporated in the
implementation of simulators for various optical disk
storage systems.
We investigate the effects of a new notion of blocking
and we show that in certain application environments,
it can improve the retrieval performance of optical
disk storage systems.
Optical disk storage media is new and not well
understood. The research presented provides answers and
new insights about the various optical disk storage
architectures and models their access performance.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (07/28/89)
Dept. of Computer Science, will speak on
``Software Portability by Virtual Machine Emulation.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Wednesday, August 2, 1989
Mr. Stefan Vorhoetter, graduate student, Dept. of
Computer Science, will speak on ``Software Portability
by Virtual Machine Emulation.''
TIME: 3:30 p.m.
ROOM: DC 1304
ABSTRACT
The proliferation of diverse computer architectures has
resulted in an increased need for portable software,
but many portability techniques incur a performance
penalty. This penalty can be reduced by restricting
the range of architectures to which a program must be
portable, at the risk of limiting portability to new
hardware as it becomes available.
In this thesis we examine a technique for making a
program portable to architectures for which it was not
intended, without affecting its performance on other
architectures. The technique used is virtual machine
emulation, whereby an ideal (for the program)
architecture is emulated by another program on an
incompatible system. By designing the virtual machine
carefully, performance loss due to emulation can be
minimized, and the program to be ported can be
recompiled for the virtual machine without
modification.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (08/11/89)
Dept. of Computer Science, will speak on
``Tuples in Imperative Programming Languages.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Friday, August 18, 1989
Mr. David Till, graduate student, Dept. of Computer
Science will speak on ``Tuples in Imperative
Programming Languages.''
TIME: 2:00 p.m.
ROOM: DC 3540
ABSTRACT
Ordered lists of heterogeneous elements, known as
tuples, appear in most imperative programming
languages, usually as parameter lists for routine
invocations or as subscript lists for array element
extraction. In this talk, other tuple contexts are
developed, and three constructs relating to them are
discussed: the multiple assignment statement, multiple
return values from routines, and input parameters
passed by means of the assignment statement.
The programming language K-W C, which implements most
of these tuple contexts and constructs, is introduced
and described.daemon@watdragon.waterloo.edu (Owner of Many System Processes) (09/06/89)
Dept. of Computer Science, will speak on ``Study of Monitors.''
From: wlrush@poppy.waterloo.edu (Wenchantress Wench Wendall)
Path: poppy!wlrush
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Friday, September 8, 1989
Mr. Michel Fortier, graduate student, Dept. of Computer
Science, will speak on ``Study of Monitors.''
TIME: 2:00 p.m.
ROOM: DC 1304
In the design of a concurrent system, problems of
synchronization and communication of processes can be
solve by using monitors.
Over the past 15 years several different kinds of
monitors have been investigated. A taxonomy is
presented that encompasses all these traditional
monitors and suggests others not found in the
literature or in existing programming languages. The
classification scheme is based on a single criterion
- the scheduling of processes waiting to use the
monitor which occurs after a wait, after a signal and
at the exit of the monitor. It identifies a total of
nine different primitive monitor types: six signal
monitors based on categorizations of
blocking/nonblocking signal and priority of
resumption, two based on immediate return signal and
priority of resumption, and two based on an automatic-
signal mechanism and priority of resumption.
An attempt is made to give some empirical discussion
and analytical results about the classification
criterion that suggest that some monitor types,
although functionally equivalent, are better than
other types. In particular, the priority-nonblocking
monitor has properties that suggest it is better than
the others.
All the monitor types have been implemented in C
language. By having the different monitor types in one
language, it was possible to run tests to compare them.
An animation facility has been implemented to
visualize the different types of monitors by
showing process movement on entry queues, on
condition variables and in and out of the monitor.
With this tool, it is possible to see the differences
in the monnitors as well as deadlock and bottlenecks.daemon@watdragon.waterloo.edu (Owner of Many System Processes) (09/07/89)
Dept. of Computer Science, will speak on
``A Model for Approximate Text Matching.''
From: wlrush@poppy.waterloo.edu (Wenchantress Wench Wendall)
Path: poppy!wlrush
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Monday, September 11, 1989
Mr. George Townsend, graduate student, Dept. of
Computer Science, will speak on ``A Model For
Approximate Text Matching.''
TIME: 3:30 p.m.
ROOM: DC 1302
ABSTRACT
This thesis introduces the concept of
Approximate Text Matching, a natural extension of
approximate string matching. A hierarchical model is
presented upon which solutions to this problem may be
based.
Traditional approaches to approximate string
matching deal with transformations which, when
applied at the string layer, cause two strings to
become equivalent at the character layer. If the
transformations required to achieve this are
"reasonable" as determined by some heuristics, the
two original strings are claimed to be approximately
equal.
This traditional model consists of two layers,
the string layer and the character layer, where the
string layer is viewed as a sequence of characters.
The typical transformations applied to the
string layer are transposition of characters,
removal of superfluous characters, and addition of
missing characters. In the model presented here,
these same notions are applied at multiple layers of
the problem. "Text" is viewed as a sequence of
"fields of data", or phrases. A "field of data" is
viewed as a sequence of "unit strings" or words. Each
"unit string" is viewed, in the traditional manner, as
a sequence of characters. The traditional
transformations considered in approximate string
matching are applied at each of these layers in a
general way.
The advantages of the model are twofold. First,
the model understands the structure of the data,
and will therefore search for matches for a
particular field in an appropriate place. Secondly, the
failure of the model at one layer is often
compensated for at the next highest layer.
The Oxford English Dictionary was used as a
testing ground for algorithms based upon this model.
Citations occurring in the body were matched against
their sources in the O.E.D. bibliography. On two
samples of data, correct matches were made over 90% of
the time.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (09/22/89)
Dept. of Computer Science, will speak on
``The Automatic Inbetweening of Keyframes Composed of
Spline Curves Satisfying Various Constraints.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Thursday, September 28, 1989
Mr. Ronald Hardock, graduate student, Dept. of Computer
Science, will speak on ``The Automatic Inbetweening of
Keyframes Composed of Spline Curves Satisfying Various
Constraints.''
TIME: 2:30 p.m.
ROOM: DC 1304
ABSTRACT
This thesis presents a method one can use to obey a
certain class of constraints between spline curves in a
keyframe inbetweening environment. The general problem
is ensuring that constraints, which are true for
keyframes, will also be true for the computer-generated
inbetween frames.
Various types of constraints are outlined. A set
of conditions on the interpolation method are outlined
such that linear mapping constraints can be obeyed.
Mention is also made of various constraints that are
not expressible as linear mappings, to point to
directions of future research.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (09/28/89)
Dept. of Computer Science, will speak on
``Hypermedia Document Information Based Retrieval Applications.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Thursday, October 5, 1989
Suzanne M. Potvin, graduate student, Dept. of Computer
Science, will speak on ``Hypermedia Document
Information Based Retrieval Application.''
TIME: 10:30 p.m.
ROOM: DC 3540
ABSTRACT
Hypermedia systems emphasize text and graphical
information and provide interactive interfaces for
browsing and editing information concepts. However,
most hypermedia systems do not provide adequate query
mechanisms.
In this presentation, we present a specification and a
prototype implementation of a hypermedia document-based
information retrieval application (HyDIRA). This
application combines the advantages of both hypertext
and document management systems, and minimizes
disadvantages related to present hypertext systems.
The prototype version that has been implemented
demonstrates the feasibility of the goals and
functionality provided by HyDIRA.
The document model used resembles the ODA/ODIF object-
oriented standard for Office Document Architectures
(although it is limited). We will present some first
feedback on how the ODA/ODIF standard could be extended
to support hypertext/hypermedia applications in an
integrated and uniform manner.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (10/12/89)
will speak on ``An Evaluation of Tension within an Extensible
Spline Testing Facility.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Monday, October 16, 1989 NOTE!! DATE CHANGE!!
Mr. Paul Ruest, graduate student, Dept. of Computer
Science, will speak on ``An Evaluation of Tension
within an Extensible Spline Testing Facility.''
TIME: 10:30 a.m.
ROOM: DC 3540 NOTE!! CHANGE OF ROOM
ABSTRACT
Beta2 and rational B-splines have received a great
deal of attention in recent years. Both associate an
extra parameter called tension with each control vertex
which allows the curve to be pulled or pushed locally,
relative to the control polygon, and independent of
control vertex movement.
An obvious question from the design point of view
is whether users actually find these tension parameters
useful. Therefore an experiment was designed and
performed to explore the usefulness of tension when
interactively designing curves.
The experiment was performed on a reworked version
of an extensible spline testing software system that
has been developed at the University of Waterloo
Graphics lab.
October 5, 1989wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (11/17/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Wednesday, November 22, 1989
Martin Van Bommel, graduate student, Dept. of Computer
Science, will speak on ``Functional Dependencies and
Join Conditions in Object-Oriented Data Models''
TIME: 2:30 p.m.
ROOM: DC 1331
ABSTRACT
Several kinds of explicit constraints for the
relational model have proven invaluable in appraising a
choice of relation schemes, in designing the physical
database, and in optimizing queries. Variations of
these constraints for object-oriented data models will
almost certainly have the same benefits. In this talk,
I will discuss two possible forms of constraints for a
simple choice of object-oriented data model. Some
preliminary results on applications of an ability to
reason about these constraints will be examined. Sound
and complete axiomatizations will be presented,
followed by an outline of decision procedures for
several special cases in which constraints satisfy
further syntactic restrictions.
November 15, 1989wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (12/01/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Tuesday, December 5, 1989
Mr. Dexter Bradshaw, graduate student, Dept. of
Computer Science, will speak on ``Retrieval
Optimization in the Minos Distributed Testbed.''
TIME: 10:30 a.m.
ROOM: DC 1331
ABSTRACT
MINOS is a distributed data management system that
supports the management of complex data objects.
Particular emphasis is given to the management of
complex multimedia data (text, voice, images, video
etc.). This thesis describes the design,
implementation and performance evaluation of algorithms
for improving the retrieval performance of the system.
Three types of performance optimizations are described.
Query evaluation performance is improved by introducing
buffering and scheduling algorithms that exploit the
sequential characteristics of the access methods used
by the system for queries involving text and attribute
searches. Data retrieval from the database server is
improved by reducing the disk exchanges in jukebox
server architectures through appropriate long term
scheduling algorithms. Finally, network traffic is
reduced by using set processing, routing and flow
control protocols between the data server and its
clients.
November 30, 1989wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (12/08/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
MASTER'S THESIS PRESENTATION
-Thursday, December 14, 1989
Ms. Yvonne Dubreuil, graduate student, Dept. of
Computer Science, will speak on ``The Integration of
Buffer Management and Recovery Management.''
TIME: 2:30 p.m.
ROOM: DC 1304
ABSTRACT
The basics of IBM's ARIES Database Recovery System will
be discussed. This system uses fuzzy checkpoints thus
all the buffers containing dirty pages do not have to
be written out during checkpointing. The cost of
checkpointing is significantly reduced especially with
the large buffer pools in use today.
Buffer Managers and Recovery Managers tend to be at
odds with each other. The buffer manager wants to keep
pages it expects to be accessed in the near future in
the buffer pool while the recovery manager wants to
write out the pages that will poorly affect its
recovery performance. I will discuss a buffer manager,
ODPF (Oldest Dirty Page First), that bases its criteria
for page replacement on data that is used by the
recovery system thus having the effect of lowering the
I/O cost of recovery even further. Performance results
based on simulation will also be presented.
December 7, 1989