Given a sequence of leaf nodes with positive weights, the optimumalphabetic binary tree can be constructed in O( nlogn) time in the worstcase and in O(n) time in most cases.The open question is: if the weight distribution is random,what percentageof cases be solved in linear time?

Harris discovered a corrrespondence between random walk excursions and random trees whose continuous analog relates a Brownian excursion to Aldous's concept of a continuum random tree. This idea has been developed and applied in various ways by Neveu, Le Gall and others.I will review these ideas in terms of a forest growth process, originallydevised by Aldous to describe the asymptotics of large finite trees, but nowrelated to the structure of a Brownian path exposed by sampling at the timesof points of an independent Poisson process.Reference: Chapter 6 of "Combinatorial Stochastic Processes", available viahttp://stat-www.berkeley.edu/users/pitman/bibliog.html

The Gross-Koblitz formula describes Gauss sums on finite fieldsof characteristic $p$ in terms of the $p$-adic Gamma function. Thisformula is a $p$-adic lifting of Stickelberger's congruence on Gauss sums.There have been several proofs of the formula (Gross-Koblitz,Dwork-Boyarsky, Katz, Coleman), which all involve some cohomologicalcalculations. Recently, a proof has been found by A. Robert which isconceptual but truly elementary, at the level of "freshman $p$-adicanalysis." We will discuss Robert's proof and describe possibleextensions

In this series of lectures, we will start with some basictheory, examples and techniques of studying occurences of patterns,and waiting times in sequences of independent Bernoulli or multinomialtrials. We will discuss some exact theory, and asymptotics, such ascentral limit theorems and Poisson approximations. We will then proceed tospecial types of coincidences, such as matching, and the problem oflook-alikes. We also hope to present some of the modern developments onlongest increasing subsequences, and applications, such as to genetics.

Potential Statistics Recruitment CandidateChange point problems have a variety of applications including industrial quality control, reliability, clinical trials, surveillance, and security systems. By monitoring data streams which are generated from the process, we are interested in quickly detecting malfunctioning once the process goes out of control, while keeping false alarms as infrequent as possible when the process is in control. Suppose that $f_ heta(x)$, the distribution of the data, is indexed by $ heta$, a vector of one or more parameters. Most research has been done under the assumption that the value of $ heta$ is known before a change occurs. In this talk, we investigate the situation where the value of $ heta$ is composite before a change occurs. We present a new formulation of the problem by specifying required average time to detect after the value of $ heta$ shifts to a specified $ heta_1$ and trying to minimize the frequency of false alarms over a range of possible value $ heta$ before a change occurs. Asymptotically optimal procedures will be presented.