Meeting Agenda - 2000.02.02
Meeting Agenda - 2000.02.02
Algorithms
and Complexity Seminar
Title:
``Improved Algorithms for Global Routing and Time-Driven Routing''
Speaker:
Guo-Hui Lin, Computer Science Graduate Student, U. of Waterloo
Time & Place: 3:30 p.m; DC1304
Abstract:
Many problems arising from physical design in VLSI technology
involve a certain kind of
minimum-cost interconnecting. These problems can
be formulated into the Steiner tree
problem or Steiner-like problems. In this talk we
present several approximation algorithms for
the Rectilinear Steiner tree problem, hexagonal
Steiner tree problem, and Steiner-like
problems asking Quality of Service (QoS). Typically
included are a faster algorithm for the
optimal Z-shaped layout of rectilinear minimum spanning
tree, a linear time algorithm for the
optimal layout of hexagonal minimum spanning tree,
a linear time algorithm for constructing
Steiner minimum tree for terminal lying on the boundary
of a hexagon, and a better algorithm
for time-driven routing in rectilinear plane. Implementation
results on standard benchmark
data show that these algorithms outperform existing
algorithms, both in performance and
practicality.
Networks Seminar
Title:
``Caching and Multicast Delivery''
Speaker:
David Evans, CS Graduate Student, U. of Waterloo
Time & place: 3:30 p.m; DC1331
Abstract:
Caching has long been used to decrease the response
time for retrieving popular pages in an
information delivery system such as the web. However,
the maintenance of cache coherency
in the face of frequently changing pages is a difficult
problem. Guaranteeing high levels of
coherency is costly both in terms of network resources
and server overhead. Even aggressive
updates of caches will always result in some minimal
staleness caused by the network delay.
This talk will discuss and attempt to quantify some
of the benefits that can be achieved if we
relax our coherency requirements. Multicast, whereby
the network infrastructure manages the
duplication of data necessary for propagating information
to multiple recipients, will be
explored as a mechanism for updating multiple caches.
A definition of staleness suitable for
measurement will be provided and simulation results
comparing on-demand multicast and
multicast push will show how network link use can
be reduced while controlling the increase
in staleness. An application displaying a rotating
image for advertisement purposes will also be
discussed, showing that increasing staleness does
not skew the fraction of requests that receive
each advertisement.
Friday, 4 February, 2000
Statistics &
Actuarial Science
Title:
Estimating change points of a near bath-tub shape hazard
Speaker: Dr. Shrikant Joshi,Department
of Statistics and Actuarial Science, University of Waterloo
Time & Place: 11:30am; MC5158
ABSTRACT
The lifetime of a manufactured item can
be more meaningfully modeled
through its hazard rate h(t)=f(t)/(1-F(t)).
A bath-tub shape hazard
rate model is appropriate when we have
high infant mortality followed
by a long useful period and then increasing
hazard rate due to aging.
The two change points of the hazard
rate are useful in deciding the
"burn-in" strategies and warranties.
In the first part of the talk
we survey the literature and indicate
how some of the developments
have led to results in more general
setup. In the second part, we
present nonparametric Bayesian treatment
of this problem; we also
indicate how a similar approach can
be employed in models involving
shape restrictions.
Nortel Networks
Institute
Title: Perspectives on Evolution of Next Generation
High-Capacity Systems
Speaker: Alan Solheim Director, Optical Network Architecture
Time: 1:00 p.m.
Place: Davis Centre, Room 1302
Abstract
Within a year, commercially proven WDM systems based on a 10 Gb/s
optical line rate will evolve to 1.6 Tb/s capacity per fiber in
terrestrial long-haul applications. Future systems must allow
many
Terabits per fiber in order to keep pace with rapidly increasing demand
and force down transport costs per bit kilometer.
This talk addresses the technologies and implementations associated
with
future multi terabit per second systems. The useable optical bandwidth
and related optical amplifier technologies, optical spectral efficiency,
modulation formats, data rates, fiber non-linearities and dispersion
will be presented in the context of possible implementations of next
generation high-capacity fiber optics transmission systems.
Ph.D.
Oral Defence (supervisor: Ming Li)
Title:
``Some String Problems in Computational Biology''
Speaker:
J. Kevin Lanctot, Ph.D. Candidate (Supervisor: Ming Li)
Time & place: 1:00 p.m. in DC1304
ICR Seminar
Title:
``Finding Short Patterns in Strings, with Applications to the Ribosome
Binding Site Problem''
Speaker: Martin
Tompa, Computer Science & Engineering, U. of Washington
Time & place: 3:30 p.m.; DC1304
Abstract
Suppose you are given 4000 strings, each of length 20. You are
told
that about one third of them contain an undisclosed pattern of length
about 5. To make matters worse, those 1300 occurrences of some
unknown
pattern are not identical substrings of length 5, but only approximately
equal substrings. Your problem is to identify the pattern.
This is not
a crisp mathematical problem, but that is not unusual for problems
that
arise in analyzing biological sequences. The particular problem
presented above arose in identifying the ribosome binding sites in
prokaryotic nucleotide sequences, but also has other applications in
biological sequence analysis. I will list some of these problems,
present an approach to solving them, and show some results of this
approach on prokaryotic ribosome binding sites. The talk will
presume
no knowledge of molecular biology.