CS-99-22 |
Title |
An Abel ODE class generalizing
known integrable classes |
Authors |
E.S. Cheb-Terrab and A.D.
Roche |
Abstract |
A multi-parameter non-constant invariant Abel ODE class with the following
remarkable features is presented. This one class is shown to generalize, that
is, contain as particular cases, all the integrable classes presented by Abel,
Liouville and Appell, as well as all those shown in Kamke's book and various
other references. In addition, the class being presented includes other new and
fully integrable subclasses, as well as the most general parameterized class we
know of whose members can systematically be mapped into Riccati type ODEs.
Finally, many integrable members of this class can be systematically mapped into
an integrable member of a different class; leading in this way to new integrable
classes from previously known ones. |
Date |
Aug 24 1999 |
Comments |
This paper has been submitted
to The European Journal of Applied Mathematics, August 1999 |
Report |
Latex |
|
Adobe
PDF |
Compressed
Latex and PostScript |
CS-99-16 |
Title |
An Evolutionary Approach to Structural Design Composition |
Authors |
Paulo Alencar, Donald Cowan, Jing Dong, Carlos Lucena |
Abstract |
One of the main goals of component-based software engineering
(CBSE) is to enable automated assembly of software components, thus bringing
greater quality and reliability, reducing development and test times,
increasing productivity from multiple use of software components in the
software development. A serious impediment for component assembly is
due to the fact that the design and architectural assumptions that a
reusable component makes about the structure of the application are in
most cases implicit, lost or buried in complex implementation structures.
In this paper we present an evolutionary approach to support the creation
of reusable and changeable software architectures which focuses on the
structural compositon of components at the design level. The architectural
design information, captured by design patterns, is made explicit and
represented in a declarative way, being packaged into tangible artifacts
as building block design components in the development process. In this
way, the declarative design component representations can be instantiated,
adapted, assembled, maintained, and implemented. Furthermore, we can
also use these representations to reason about properties related to the
combination of design components. Our approach is illustrated through
a case study involving various design patterns
|
Date |
|
Comments |
|
Report |
|
|
Adobe
PDF |
|
CS-99-14 |
Title |
Better Pasting Through
Quasi-Interpolation |
Authors |
B. Conrad |
Abstract |
Hierarchical surface pasting,
developed by Barghiel, Bartels and Forsey, is an interactive surface modelling
technique that is used to add local detail to a tensor product B-spline
surface without increasing the overall complexity of the original surface.
Surface pasting approximates displacement mapped surfaces by placing additional
tensor product surfaces, called features, on the base surface. The features
may be scaled, rotated, and translated arbitrarily over the base surface,
and the composite surface can be evaluated using relatively little computational
power. Because the feature only approximates a displacement map, a surface
produced using standard surface pasting often has noticeable gaps at the
edges of the pasted feature. The severity of the surface discontinuities
may be made as small as desired via knot insertion, but this can result
in an unacceptable degradation in the performance of the modelling software.
Quasi-interpolation is an approximation method that approximates curves
with spline curves to a high degree of accuracy. The approximation is constructed
by computing coefficients that are used to weight samplings of the curve
to be approximated. The Lyche-Schumaker quasi-interpolant uses coefficients
that are inexpensive to compute and samplings that are relatively expensive
to compute. I propose an improved surface pasting technique that uses quasi-interpolation
to set the feature's boundary control vertices. For surface pasting it is
necessary to have quasi-interpolants that reproduce position and derivatives
at the endpoints of the curve to be approximated. In addition, as the feature
surface is moved, the curve samplings must be recomputed, but the coefficients
remain fixed. Therefore, I have developed a variation of the quasi-interpolant
whose coefficients are expensive to compute, but whose samplings are relatively
inexpensive to compute.
Surface pasting with quasi-interpolation produces features whose boundaries
approximate the base surface to within the same tolerance as those produced
by standard pasting, but with one third the boundary control vertices. The
resulting feature has one ninth the total control vertices and can be constructed
in approximately one tenth the time as with standard surface pasting. |
Date |
May 1999 |
Report |
|
|
Adobe
PDF |
Compressed
PostScript |
CS-99-09 |
Title |
Resizable Arrays in Optimal
Time and Space |
Authors |
A. Brodnik, S. Carlsson,
E.D. Demaine, J.I. Munro and R. Sedgewick |
Abstract |
We present simple, practical
and efficient data structures for the fundamental problem of maintaining
a resizable one-dimensional array, A[l...l+n-1], of fixed-size elements,
as elements are added to or removed from one or both ends. In addition to
these operations, our data structures support access to the element in position
i. All operations are performed in constant time. The extra space (i.e.,
the space used past storing the n current elements) is O(sqrt(n)) at any
point in time. This is shown to be within a constant factor of optimal,
even if there are no constraints on the time. If desired, each memory block
can be made to have size 2^k - c for a specified constant c, and hence the
scheme works effectively with the buddy system. The data structures can
be used to solve a variety of problems with optimal bounds on time and extra
storage. These include stacks, queues, randomized queues, priority queues,
and deques.
|
Date |
September 2000 |
Comments |
A short version of this
paper appears in Proceedings of the 6th International Workshop on Algorithms
and Data Structures (WADS'99), edited by Frank Dehne, Arvind Gupta, Jvrg-R|diger
Sack, and Roberto Tamassia, Lecture Notes in Computer Science, volume 1663,
Vancouver, British Columbia, Canada, August 11-14, 1999, pages 37-48.
|
Report |
|
|
Adobe
PDF |
Compressed
PostScript |
CS-99-05 |
Title |
Evaluating Tests for Input
Stuck-at Faults in Word-Oriented Static Random-Access Memories |
Authors |
P.R. Sidorowicz |
Abstract |
An evaluation of well-known
tests: Mats+, Mats++, March Y and March C- with respect to input stuck-at
faults in a n-word by l-bit static CMOS random-access memory (SRAM) array
is presented. First, an SRAM cell's behavior is analysed at the transistor-network,
event-sequence, and finite-state machine (FSM) level. Then, an input stuck-at
fault model for an SRAM is defined. We show that the word oriented extensions
of the above-mentioned tests detect reliably at most (n+4l)/(2n+4l)*100%
of faults in our fault model, which for large n constitutes roughly 50%
of faults. We propose a DFT enhancement that would increase this coverage
to 100%.
Keywords:CMOS, design for testability, fault modeling, March C-,
March Y, Mats+, Mats++, SRAM, stuck-at faults, testing. |
Date |
March 1999 |
Comments |
This research was supported
by the Natural Sciences and Engineering Research Council of Canada under
grant No. OGP0000871. |
Report |
|
|
Adobe
PDF |
Compressed
PostScript |
CS-99-04 |
Title |
Ununfoldable Polyhedra |
Authors |
Marshall Bern (Xerox PARC)
Erik D. Demaine (University of Waterloo)
David Eppstein (University of California, Irvine)
Eric Kuo (MIT) |
Abstract |
A well-studied problem
is that of unfolding a convex polyhedron into a simple planar polygon. In
this paper, we study the limits of unfoldability. We give an example of
a polyhedron with convex faces that cannot be unfolded by cutting along
its edges. We further show that such a polyhedron can indeed be unfolded
if cuts are allowed to cross faces. Finally, we prove that ``open'' polyhedra
with convex faces may not be unfoldable no matter how they are cut. |
Date |
August 1999 |
Comments |
This paper appears in
the electronic proceedings of the 11th Canadian Conference on Computational
Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15-18, 1999.
We are pursuing these problems further; please contact the authors if you
make any progress. |
Report |
|
|
Adobe
PDF |
Compressed
PostScript |
CS-99-03 |
Title |
Convexifying Monotone
Polygons |
Authors |
Therese C. Biedl (University
of Waterloo)
Erik D. Demaine (University of Waterloo)
Sylvain Lazard (INRIA Lorraine)
Steven M. Robbins (McGill University)
Michael A. Soss (McGill University) |
Abstract |
This paper considers reconfigurations
of polygons, where each polygon edge is a rigid link, no two of which can
cross during the motion. We prove that one can reconfigure any monotone
polygon into a convex polygon; a polygon is monotone if any vertical line
intersects the interior at a (possibly empty) interval. Our algorithm computes
in O(n^2) time a sequence of O(n^2) moves, each of which rotates just four
joints at once. |
Date |
December 1999 |
Comments |
A version of this paper
appears in Proceedings of the 10th Annual International
Symposium on Algorithms and Computation (ISAAC'99), Lecture Notes in Computer
Science, Springer-Verlag, volume 1741, Chennai, India, December 16-18, 1999,
pages 415-424.
|
Report |
|
|
Adobe
PDF |
Compressed
PostScript |