Monday, June 1, 2015
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Quicksort is a venerable sorting algorithm,
it is taught in basic algorithms classes, and
it is routinely used in practice.
Can there be anything new about Quicksort today?
\emph{Dual-pivot quicksort} refers to variants of classical quicksort
where in the partitioning step two pivots are used to split the input
into three segments.
Algorithms of this type received quite some attention starting from
2009,when a dual-pivot algorithm due to Yaroslavskiy, Bentley, and Bloch
replaced the well-engineered quicksort algorithm in Oracle's Java 7
runtime library.
An analysis by Nebel and Wild from 2012 gave $1.9\ln n$
comparisons on average for $n$ input numbers. (Other works ensued.)
We consider a model that captures all dual-pivot methods,
give a general analysis and identify an algorithm with the minimum
average number of key comparisons (which is $1.8n \ln n - 2.38...n +
O(\log n)$).
The expected number of comparisons can even be determined exactly.
We also comment on the more general situation when $k>2$ pivots are
used, and on other performance measures than comparisons.
(Based on joint work with Martin Aumüller, Daniel Krenn, Clemens
Heuberger, and Helmut Prodinger)
Colloquium - 16:00
Abstract:
The associahedron is a polytope whose face lattice encodes the combinatorics of
diagonals of a convex polygon in the plane. It was generalized to many
directions. Among them are the so called generalized associahedra related to
cluster algebras on one hand, and graph associahedra on the other hand. Trying
to construct various non-equivalent geometrical representatives of these
polytopes raises many beautiful combinatorial problems. Realizing them as
complete fans (set of polyhedral cones covering their ambient space) is a first
step and is a little weaker than as polytopes, but still geometric. In a paper
with Cesar Ceballos and Günter Ziegler, Francisco Santos gave a construction of
many different (usual) associahedra, which begins with constructing their fan
and turns out to be based on the denominator vectors in the framework of
cluster algebras of type A. In this talk, I will present a construction of fans
realizing graph associahedra, which in the case of the usual associahedron is
the one of Francisco Santos. The construction, specified to the case of a cycle
associahedron (cyclohedron) extends this of Francisco Santos to the generalized
associahedron of type B, still with an interpretation as denominator vectors,
and allows in both cases (types A and B ) to derive the polytopality of the
the one of Francisco Santos. The construction, specified to the case of a cycle
associahedron (cyclohedron) extends this of Francisco Santos to the generalized
associahedron of type B, still with an interpretation as denominator vectors,
and allows in both cases (types A and B ) to derive the polytopality of the
fans. In the talk, I will insist on the combinatorial aspects of the
construction.
(joint work with Vincent Pilaud arXiv:1501.07152)