Speaker: Maverick Woo
Title: Finger Search on Balanced Search Trees
Date: 2006-04-14, Friday
Time: 15:30
Place: Wean 5409
Committee:
Guy E. Blelloch, Carnegie Mellon University, co-chair
Richard Cole, New York University
Bruce M. Maggs, Carnegie Mellon University, co-chair
Daniel Dominic Kaplan Sleator, Carnegie Mellon University
Abstract:
This thesis introduces the concept of a heterogeneous decomposition of a balanced search tree and apply it to the following problems:
* How can finger search be implemented without changing the representation of a Red-Black Tree, such as introducing extra storage to the nodes?
(Answer: Any degree-balanced search tree can support finger search without modification in its representation by maintaining an auxiliary data structure of logarithmic size and suitably modifying the search algorithm to make use of this auxiliary data structure.)
* Do MultiSplay Trees, which is known to be O(log log n)-competitive to the optimal binary search trees, have the Dynamic Finger property?
(Answer: This is work in progress. We believe the answer is yes.)
WEDNESDAY, April 26, 2006
PROBABILITY IN SCIENCE AND INDUSTRY SEMINAR
4:30 P.M., WeH 7500
Philippe Robert, INRIA, Rocquencourt.
TITLE: Data Structures, Tree Algorithms and Renewal Theorems
ABSTRACT: A tree algorithm is a procedure that divides (splits) recursively into subsets an initial set of n items until each of the subsets obtained has a cardinality strictly less than some fixed number D. These algorithms have a wide range of applications: access protocols in communication networks, divide and conquer algorithms for data structures, leader election in distributed systems, … The asymptotic behavior of additive cost functions associated to these algorithms is presented. When the successive splittings are assumed to be independent then, via an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to complex analysis techniques as it is usually the case in this domain. When the successive splittings are not anymore independent but only stationary (dynamical source), it is shown the entropy function of the dynamical system determines the asymptotical behavior of the cost function. The key ingredient of all these results is a generalized renewal theorem.
Joint work with Mohamed.
Refreshments at 4:00 WeH 6220.
Speaker: Varun Gupta
Time: Wednesday 12-1pm
Place: NSH 1507
Title: A gentle introduction to fluid and diffusion limits for queues
Abstract:
To obtain explicit results in queueing theory, it is almost always necessary to make certain strong assumptions about the statistical nature of the process involved. These assumptions are only approximately satisfied in practice, if at all. However, under certain limiting cases one can get results that do hold under weaker conditions. One such condition is when the system is operating close to its maximum capacity or is overloaded. In the latter case, appropriately time and space scaled versions of the stochastic process converge to what are known as fluid and diffusion processes. In my talk, I will informally review the notion of fluid and diffusion limits and illustrate them using examples of non-stationary queues.
