#
Monday Lecture and Colloquium

**Monday, May 21, 2012 **

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

### Raimund Seidel - Universität des Saarlandes, Saarbrücken

### Analyzing String Sorting Algorithms

*Abstract:*

How expensive is it to quicksort a set $S$ of $n$ strings
taking into account that the cost of comparing two strings
depends on the length of their common prefix? Clearly
$O(n\log n)$ is not the right bound. It is too small. How do
you even express a reasonably tight bound? Traditional
parameters such as $n$, the number of strings in $S$,
and $m$, their cumulative length, are easily seen to be
inappropriate. We will show that the \emph{thickness vector,}
a parameter set associated with the trie of $S$, allows
to express the expected cost of quicksorting $S$ in a very
precise manner. The same holds for other sorting methods as
well, and even for lower bounds.

** Colloquium - 16:00**

### Nicolai Hähnle -
EPFL

### The diameter of polyhedra and volume expansion

*Abstract:*

The well-known Simplex method for linear programming walks along the vertex-
edge graph of a polyhedron. How quickly can an optimal vertex be reached in
this way? The polynomial Hirsch conjecture claims that there always exists a
path whose length is bounded by a polynomial in the number of facets and the
dimension (though it makes no claims about how to find such a path!).

We briefly outline some approaches to this problem and then discuss a new upper
bound for polyhedra defined by a system of inequalities whose coefficient matrix
has bounded subdeterminants. This is joint work with N. Bonifas, M. Di Summa,
F. Eisenbrand, and M. Niemeier.

Letzte Aktualisierung:
15.05.2012