Forthcoming events in this series


Tue, 16 Oct 2007
16:30
SR1

The structure and profile of digital trees

Nicolas Broutin
(McGill)
Abstract

Digital trees is a general structure to manipulate sequences of characters. We propose a novel approach to the structure of digital trees.

It shades some new light on the profile of digital trees, and provides a unified explanation of the relationships between different kinds of digital trees. The idea relies on the distinction of nodes based on their type, i.e., the set of their children. Only two types happen to matter when studying the number of nodes lying at a specified level: the nodes with a full set of children which constitutes the core, and the nodes with a single child producing spaghetti-like trees hanging down the core. We will explain the distinction and its applications on a number of examples related to data structures such as the TST of Bentley and Sedgewick.

This is joint work with Luc Devroye.

Tue, 16 Oct 2007
14:30
L3

Combinatorial Problems in Conservation Biology

Charles Semple
(University of Canterbury, NZ)
Abstract
A central task in conservation biology is measuring, predicting, and preserving biological diversity as species face extinction. Dating back to 1992, phylogenetic diversity is a prominent notion for measuring the biodiversity of a collection of species. This talk gives a flavour of some the combinatorial and algorithmic problems and recent solutions associated with computing this measure. This is joint work with Magnus Bordewich (Durham University, UK) and Andreas Spillner (University of East Anglia, UK).
Tue, 09 Oct 2007
14:30
L3

Tying down the diameter of G(n,p).

Bruce Reed
(McGill/INRIA/CNRS))
Abstract
We show that the diameter of G(n,p) is concentrated on one of three values provided the average degree p(n-1) goes to infity with n. This is joint work with N. Fountoulakis even though he refuses to admit it.