CS200126  

Title  Finding Hidden Independent Sets in Interval Graphs  
Authors  T. Biedl, B. Brejova, E. D. Demaine, A. M. Hamel, A. LopezOrtiz, T. Vinar  
Abstract  We design efficient competitive algorithms for discovering information hidden by an adversary. Specifically, consider a game in a given interval graph $G$ in which the adversary chooses an independent set $X$ in $G$. Our goal is to discover this hidden independent set $X$ by making the fewest queries of the form ``Is point $p$ covered by an interval in $X$?'' Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a onedimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it $X$?) and the discovery scenario (find $X$ without any information). Under some assumptions on the interval graph, these algorithms use an asymptotically optimal number of queries in every instance.  
Date  December 2001  
Report  Finding Hidden Independent Sets in Interval Graphs (PDF) 
Compressed
PostScript: 
CS200125  

Title  A Direct Algorithm to Constract the Minimal Telescopers for Rational Functions (qDifference Case)  
Authors  H.Q. Le, S.A. Abramov and K.O. Geddes  
Abstract  In this paper we present a direct algorithm to construct the minimal telescopers for rational functions for the qdifference case.  
Date  November 2001  
Report  A Direct Algorithm to Constract the Minimal Telescopers for Rational Functions (qDifference Case) (PDF) 
Compressed
PostScript: A Direct Algorithm to Constract the Minimal Telescopers for Rational Functions (qDifference Case) (PS.Z) 
CS200124  

Title  HypergeometricSum: A Maple Package for Finding Closed Forms of Indefinite and Definite Sums of Hypergeometric Type  
Authors  H.Q. Le, S.A. Abramov and K.O. Geddes  
Abstract  We describe the Maple module HypergeometricSum which provides various tools for finding closed forms of indefinite and definite sums of hypergeometric type, and for certifying a large class of combinatorial identities. The document is intended both as an an elementary introduction to the subject and as a reference manual for the module.  
Date  November 2001  
Report  HypergeometricSum: A Maple Package for Finding Closed Forms of Indefinite and Definite Sums of Hypergeometric Type (PDF) 
Compressed
PostScript: HypergeometricSum: A Maple Package for Finding Closed Forms of Indefinite and Definite Sums of Hypergeometric Type (PS.Z) 
CS200123  

Authors  L. Stanchev  
Abstract  In this paper we introduce bag relational algebra with aggregation over a particular representation of incomplete information called ctables. The ctable representation is an extension of the Codd relational model with richer semantics for null values. The reason ctables were chosen for our exploration is that they are the least expressive relational representation of incomplete information over which relational algebra is closed and can be "well defined". We justify the need for duplicate preserving relational algebra over this representation of incomplete information by introducing aggregation over ctables with duplicates.  
Date  October 2001  
Comments  This report was generated as part of a project for a 700 level course at the University of Waterloo, Waterloo, ON, Canada  
Report 
Compressed
PostScript: Codd tables with duplicates (PS)  Codd tables with duplicates (PDF) 
CS200122  

Title  Evolution of Recurrent Neural Networks to Control Autonomous Life Agents  
Authors  T. AbouAssaleh  
Abstract  Studies of artificial life (alife) attempt to simulate simple living beings. On the other hand, autonomous agents researchers are interested in building agents that are able to complete a particular task without supervision. In this research, these two areas of artificial intelligence are combined together into what we call "Autonomous Life Agent" (ALA). ALA is an artificial agent that is sent to some environment to live in without any supervision or any predefined behaviour rules. The primary goal of the agent is to learn how to survive in the artificial environment it lives in. In this research, we utilize a recurrent neural network to determine the agent's actions. A novel ALA Training System was developed that evolves recurrent neural networks using genetic algorithms. The resulting agents are capable of living in multiple similar worlds starting from random initial positions as well as in worlds that are unseen during the training.  
Date  October 2001  
Comments 
Source
code
of
the
ALA
Training
System
is
available
upon
request.
Appears in: Tony AbouAssaleh, Jianna Zhang, and Nick Cercone. 2001. "Evolution of Recurrent Neural Networks to Control Autonomous Life Agents." Proceedings of the Genetic and Evolutionary Computation Conference, GECCO2001. San Francisco, CA: Morgan Kaufmann Publishers. Page 903. Please direct all comments and suggestions to the author  
Report  Evolution of Recurrent Neural Networks to Control Autonomous Life Agents (PDF) 
CS200121  

Authors  A. LopezOrtiz  
Date  October 2001  
Report  Only available in printed format 
CS200120  

Authors  A. LopezOrtiz  
Date  October 2001  
Report  Only available in printed format 
CS200119  

Authors  P.A.S. Ward  
Date  #issued July 4, 2001,  
Report  Only available in printed format 
CS200118  

Title  A Behavioral Analysis Approach to PatternBased Composition  
Authors  Jing Dong, Paulo S.C. Alencar and Donald D. Cowan  
Date  June 2001  
Report  A Behavioral Analysis Approach to PatternBased Composition (PDF) 
CS200117  

Title  User's Manual as a Requirements Specification  
Authors  D.M. Berry, K. Daudjee, J. Dong, M.A. Nelson and T.Nelson  
Date  May 2001  
Report  User's Manual as a Requirements Specification (PDF) 
Compressed
PostScript: User's Manual as a Requirements Specification (PS.Z) 
CS200116  

Authors  D. Toman  
Date  # issued May 16th  
Report  Only available in printed format 
CS200115  

Title  Finding Shortest Paths in Large Network Systems  
Authors  E.P.F. Chan and N. Zhang  
Date  May 2001  
Report  Finding Shortest Paths in Large Network Systems (PDF) 
Compressed
PostScript: Finding Shortest Paths in Large Network Systems (PS.Z) 
CS200114  

Title  Optimal Arrangement of Leaves in the Tree Representing Hierarchical Custering of Gene Expression Data  
Authors  T. Biedl, B. Brejova, E.D. Demaine, A.M. Hamel and T. Vinar  
Abstract  In this paper, we study how to present gene expression data to display similarities by trying to find a linear ordering of genes such that genes with similar expression profiles will be close in this ordering. In general, finding the best possible order is intractable. Therefore we assume that hierarchical clustering has been applied to the gene expression profiles, and show that the best order respecting the clustering can be computed efficiently. We perform experiments comparing the optimal order to several other methods. The implementation of the algorithm, as well as a simple program for viewing hierarchically clustered expression array data and the complete results of our experiments are available at http://monod.uwaterloo.ca/supplements/01expr/  
Comments 
The paper will be submitted to WABI 2001.  
Report  Optimal Arrangement of Leaves in the Tree Representing Hierarchical Custering of Gene Expression Data (PDF) 
Compressed
PostScript: Optimal Arrangement of Leaves in the Tree Representing Hierarchical Custering of Gene Expression Data (PS.Z) 
CS200113  

Title  ProcessBased Representation and Analysis of Framework Instantiation  
Authors  Paulo S. C. Alencar, Donald D. Cowan, Toacy C. Oliviera, Carlos J. P. Lucena  
Abstract  Objectoriented frameworks are currently regarded as a promising technology for reusing designs and implementations. However, developers find there is still a steep learning curve when extracting the design rationale and understanding the framework documentation during framework instantiation. Thus, instantiation is a costly process in terms of time, people and other resources. These problems raise a number of questions including: "How can frameworks be instantiated more quickly and with greater ease? How can the same highlevel design abstractions that were used to develop the framework be used during framework instantiation instead of using source code as is done currently? How can we capture the designers' knowledge of the framework in order to compensate for the loss of key development personnel? How can we raise the level of abstraction in which the framework evolution and instantiation is expressed, reasoned about and implemented?" In this paper we present a processbased approach to framework instantiation that addresses these issues. Our main goal is to represent the framework architectural design models in an explicit and declarative way, and support changes to this architecture based on explicit instantiation processes and activities while maintaining system integrity, invariants, and general constraints. In this way, the framework instantiation and evolution can be performed in a valid and controlled way. To accomplish our goal, we introduce a processoriented description of framework instantiation as well as a formal specification of these processes that allows us to reason about instantiation using model checking techniques. Discovering instantiation errors and analyzing alternative architectures and designs early in the development process could certainly lower the cost and effort in fixing them. Various forms of analysis can be performed using our approach to check properties such as: structural evolution properties, pre and postconditions of an instantiation, the validity of the processes associated with extension points, the order of the instantiation processes, the safety and liveness of these processes, reachability, and deadlocks. We illustrate our approach with DrawingTool, a framework to provide drawing features of a case tool.  
Report  ProcessBased Representation and Analysis of Framework Instantiation (PDF) 
CS200112  

Title  A Framework For Community Information Systems  
Authors  Martin Luo, Paulo S. C. Alencar, Donald D. Cowan  
Abstract  In this paper we present a generic framework architecture for webbased community information systems (CIS). The framework has an open architecture based on COTS (commercialofftheshelf) software components and network technologies. We discuss how a componentbased approach, a layered architecture model, and design patterns can be used to provide a common framework for CIS. The CIS framework architecture results in significant benefits that include reuse, a flexible user interface, powerful search mechanisms and an integrated and scalable architecture, XML and rulebased StyleSheet languages are used for storage, information search and graphical presentation at the server or client. The overall framework architecture, its individual components and the interaction among these components are outlined.  
Report  A Framework For Community Information Systems (PDF) 
CS200111  

Title  Monotonicity Preserving and Total Variaion Diminishing Multigrid Time Stepping Methods  
Authors  A. Jameson and J.W.L. Wan  
Abstract  We propose a fast multiplicative and additive multigrid time stepping schemes for solving linear and nonlinear wave equations in one dimension. The idea is based on an upwind biased interpolation and residual restriction operators, and a nonstandard coarse grid update formula for linear equations. We prove that the twolevel schemes preserve monotonicity and are total variation diminishing, and the same results hold for the multilevel additive scheme. We generalize the idea to nonlinear equations by solving local Riemann problems. We demonstrate numerically that these schemes are essentially nonoscillatory, and that the optimal speed of wave propagation of 2^M1 is achieved, where M is the number of grids.  
Date  April 2001  
Comments 
Conference presentation: Tenth Copper Mountain Conference on Multigrid Methods Also appear in virtual proceedings at MGNET.  
Report  Monotonicity Preserving and Total Variaion Diminishing Multigrid Time Stepping Methods (PDF) 
Compressed
PostScript: Monotonicity Preserving and Total Variaion Diminishing Multigrid Time Stepping Methods (PS.Z) 
CS200110  

Title  Using OpenGL for Video Streaming  
Authors  P. Gilhuly  
Abstract 
The
process
of
streaming
digital
video
is
difficult
due
to
the
large
amount
of
data
inherent.
Previously,
without
specialized
hardware,
video
output
has
been
limited
to
low
resolution
or
slow
playback,
as
measured
by
frames
per
second.
Many of the functions of a video decoder can be mapped to the capabilities of a graphics card. However, for the graphics work involved with digital video a graphics card is required while a video decoder card is not. This thesis proposes a method to use common graphics cards, through the OpenGL API, for the task of video streaming.  
Date  April 2001  
Comments 
I
have
included
the
video
sequences
I
used
to
test
my
compressor
and
streamer
as
well
as
a
PostScript
and
a
PDF
format
of
my
thesis.
Under
the
directories
Hier
and
BFI
you
will
find
uncompressed
AVIs
(subsequently
gzipped)
of
the
frames
generated
by
my
streamer.
Under
the
directory
MPEG
you
will
find
MPEG
1
encoding
of
the
three
movies,
compressed
using
default
settings.
MPEG/*

MPEG1
encoded
versions
of
animations  
Report 
MPEG: ball, geri, tree (MPV) 
Compressed
AVI: geri_br (GZIP), tree_br (GZIP), geri_hi (GZIP), tree_hi (GZIP)  Using OpenGL for Video Streaming (PDF) 
Compressed
PostScript: Using OpenGL for Video Streaming (GZIP) 
CS200109  

Title  Evaluation of Buffer Queries in Spatial Databases  
Authors  E.P.F. Chan  
Date  April 2001  
Report  Evaluation of Buffer Queries in Spatial Databases (PDF) 
Compressed
PostScript: Evaluation of Buffer Queries in Spatial Databases (PS.Z) 
CS200108  

Title  Justintime subgrammar extraction for HPSG  
Authors  V. Keselj  
Abstract 
We
define
the
basic
problem
of
subgrammar
extraction
for
headdriven
phrase
structure
grammars
(HPSG)
in
the
following
way: Given a large HPSG grammar G and a set of words W, find a small subgrammar of G that accepts the same set of sentences from W^* as G, and for each of them produces the same parse trees. The set of words W is obtained from a piece of text. Additionally, we assume that this operation is done ``justintime,'' i.e., just before parsing the text. This application requires that this operation be done in an automatic and efficient way. After defining the problem in the general framework, we discuss the problem for contextfree grammars (CFG), and give an efficient algorithm for it. We show that finding the smallest subgrammar for HPSGs is an NPhard problem, and give an efficient algorithm that solves an easier, approximate version of the problem. We also discuss how the algorithm can be efficiently implemented.  
Date  March 2001  
Report  Justintime subgrammar extraction for HPSG (PDF) 
Compressed
PostScript: Justintime subgrammar extraction for HPSG (PS.Z) 
CS200107  

Authors  A. Garcia and D.D. Cowan  
Date  March 2001  
Report  Only available in printed format 
CS200106  

Title  Text Structure Recognition using a Region Algebra  
Authors  M. YoungLai  
Abstract 
We
consider
the
problem
of
incrementally
developing
a
parser
for
text
structure.
This
means
building
the
parser
specification
a
piece
at
a
time
while
simultaneously
developing
our
understanding
of
the
text.
We argue that existing solutions have usability and efficiency problems for this application and propose an alternative approach based on the type of region algebra that is often used as a query language for text databases. This is an appropriate interface for incremental development, but has no efficient batch parsing model such as those that exist for grammars. In this thesis, we propose an efficient batch parsing model and characterize the region algebras to which it applies.  
Date  February 2001  
Report  Text Structure Recognition using a Region Algebra (PDF) 
Compressed
PostScript: Text Structure Recognition using a Region Algebra (GZIP) 
CS200105  

Title  Modular HPSG  
Authors  V. Keselj  
Abstract 
We
present
a
detailed
description
of
the
modular
Headdriven
Phrase
Structure
Grammar
(HPSG).
Although
the
notion
of
modularity
is
known
in
the
area
of
programming
languages,
and
it
is
described
for
contextfree
grammars
(CFG),
this
is
the
first
attempt
of
defining
modularity
for
HPSGs.
We describe and formally define modularity for an HPSGtype grammar, and we illustrate its application on an example.  
Date  February 2001  
Report  Modular HPSG (PDF) 
Compressed
PostScript: Modular HPSG (PS.Z) 
CS200104  

Title  Optimum Multidimensional Interval Routing Schemes on Networks with Dynamic Cost Links  
Authors  Y. Ganjali  
Abstract 
One
of
the
fundamental
tasks
in
any
distributed
computing
system
is
routing
messages
between
pairs
of
nodes.
An
Interval
Routing
Scheme
(IRS)
is
a
space
efficient
way
of
routing
messages
in
a
network.
The
problem
of
characterizing
graphs
that
support
an
IRS
is
a
wellknown
problem
and
has
been
studied
for
some
variants
of
IRS.
It
is
natural
to
assume
that
the
costs
of
links
may
vary
over
time
(dynamic
cost
links)
and
to
try
to
find
an
IRS
which
routes
all
messages
on
shortest
paths
(optimum
IRS).
In
this
paper,
we
study
this
problem
for
a
variant
of
IRS
in
which
the
labels
assigned
to
the
vertices
are
dary
integer
tuples
(ddimensional
IRS).
The
only
known
results
in
this
case
are
for
specific
graphs
like
hypercubes,
ndimensional
grids,
or
for
the
onedimensional
case.
We
give
a
complete
characterization
for
the
class
of
networks
supporting
multidimensional
strict
and
linear
(which
is
a
variation
of
IRS)
interval
routing
schemes
with
dynamic
cost
links. Keywords: Interval routing, networks, routing algorithms, dynamic, multidimensional, characterization.  
Date  March 2001  
Report  Optimum Multidimensional Interval Routing Schemes on Networks with Dynamic Cost Links (PDF) 
Compressed
PostScript: Optimum Multidimensional Interval Routing Schemes on Networks with Dynamic Cost Links (PS.Z) 
CS200103  

Title  Characterization of Networks Supporting Multidimensional Linear Interval Routing Schemes  
Authors  Y. Ganjali  
Abstract 
An
Interval
routing
scheme
(IRS)
is
a
wellknown,
space
efficient
routing
strategy
for
routing
messages
in
a
distributed
network.
In
this
scheme,
each
node
of
the
network
is
assigned
an
integer
label
and
each
link
at
each
node
is
labeled
with
an
interval.
The
interval
assigned
to
a
link
l
at
a
node
v
indicates
the
set
of
destination
addresses
which
should
be
forwarded
through
l
from
v.
A
Multidimensional
Interval
Routing
Scheme
(MIRS)
is
a
generalization
of
IRS
in
which
each
node
is
assigned
a
multidimensional
label
(which
is
a
list
of
d
integers
for
the
ddimensional
case).
The
labels
assigned
to
the
links
of
the
network
are
also
multidimensional
(a
list
of
d
onedimensional
intervals).
The
class
of
networks
supporting
linear
IRS
(in
which
the
intervals
are
not
cyclic)
is
already
known
for
the
onedimensional
case
[FG94].
In
this
paper,
we
generalize
this
result
and
completely
characterize
the
class
of
networks
supporting
linear
MIRS
(or
MLIRS)
for
a
given
number
of
dimensions
d.
We
show
that
by
increasing
d,
the
class
of
networks
supporting
MLIRS
is
strictly
expanded.
We
also
give
a
characterization
of
the
class
of
networks
supporting
strict
MLIRS,
which
is
a
modified
version
of
MLIRS.  
Date  March 2001  
Comments  Will be submitted to SIROCCO 2001  
Report  Characterization of Networks Supporting Multidimensional Linear Interval Routing Schemes (PDF) 
Compressed
PostScript: Characterization of Networks Supporting Multidimensional Linear Interval Routing Schemes (PS.Z) 
CS200102  

Title  Reducing the Size of Auxiliary Data Needed to Maintain Materialized Views by Exploiting Integrity Constraints  
Authors  L. Stanchev  
Abstract 
A
data
warehouse
consists
of
materialized
views,
which
contain
derived
data
from
several
data
sources.
The
advantage
of
using
materialized
views
is
that
they
contain
the
results
of
standard
queries
and
therefore
when
such
queries
are
posed,
the
data
sources
those
queries
are
based
on,
which
are
usually
costly
to
access
because
of
their
size
and
remoteness,
don't
have
to
be
accessed.
However
in
order
for
the
materialized
views
to
contain
uptodata
data
they
have
to
be
updated
periodically.
Such
synchronization
of
the
materialized
views
with
the
data
sources
could
be
slow
if
the
later
have
to
be
queries
for
a
correct
update
to
be
done

i.e.
if
just
the
data
for
the
changes
done
to
the
data
sources
is
insufficient.
A
way
querying
the
data
sources
during
materialized
view
update
can
be
avoided
is
by
storing
any
data
from
the
data
sources,
which
could
be
relevant
to
an
update
of
the
materialized
views,
on
the
data
warehouse
site.
Such
auxiliary
data
is
stored
in
auxiliary
views
and
has
the
characteristic
that
it
makes
the
data
stored
at
the
data
warehouse
selfmaintainable,
i.e.
it
can
be
update
correctly
from
the
log
of
changes
done
to
the
the
data
sources.  
Date  September 2001  
Comments  It was submitted to CASCON 2000 as a paper but it was not accepted. The reported was created as a result of 700 level distributed database course at the University of Waterloo thought by Prof. Ken Salem.  
Report  Reducing the Size of Auxiliary Data Needed to Maintain Materialized Views by Exploiting Integrity Constraints (PS) 
Compressed
PostScript: Reducing the Size of Auxiliary Data Needed to Maintain Materialized Views by Exploiting Integrity Constraints (PS.Z) 
CS200101  

Title  Issues in Scalable DistributedSystem Management  
Authors  P.A.S. Ward  
Abstract 
Distributedsystem
management
concerns
the
observation
of
a
distributed
computation
and
then
using
the
information
gained
by
that
observation
to
control
the
computation.
This
necessitates
collecting
the
information
required
to
determine
the
partial
order
of
execution,
and
then
reasoning
about
that
partial
order.
This
in
turn
requires
a
partialorder
data
structure
and,
if
the
reasoning
is
being
performed
by
a
human,
a
system
for
visualizing
that
partial
order.
Both
creating
such
a
data
structure
and
visualizing
it
are
hard
problems. Current partialorder data structure techniques suffer various shortcomings. Potentially scalable mechanisms, such as Ore timestamps, are static. Dynamic algorithms, on the other hard, either require a significant search operation to answer basic questions, or they require a vector of size equal to the width of the partial order for each element stored in the order. Scalable visualization of a partial order is hard for the same reasons that drawing any large graph is hard. Any visualization that will be meaningful to a user requires appropriate abstractions on the data structure, while preserving the core meaning of the data structure. Such abstraction is difficult. This report formalizes these problems and identifies the specific difficulties that must be solved to enable scalable distributedsystem management. Keywords: distributedsystem observation, partialorder data structure, vector timestamp, datastructure visualization, scalability  
Date  January 2001  
Report  Issues in Scalable DistributedSystem Management (PDF) 
Compressed
PostScript: Issues in Scalable DistributedSystem Management (PS.Z) 