Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 21.03.2016 at 12:20 in S8, there is the following noon lecture:

A new combinatorial Gray code for balanced combinations

Torsten Mütze

Abstract

(joint work with Christoph Standke and Veit Wiechert)

Efficiently generating all objects in a particular combinatorial class (e.g. subsets, permutations, partitions, strings, trees, triangulations etc.) in such a way that each object is generated exactly once is one of the oldest and most fundamental problems in the area of combinatorial algorithms, and such generation algorithms are used as core building blocks in a wide range of practical applications. In this talk I present a new combinatorial Gray code and a corresponding time- and space-optimal algorithm for generating balanced combinations, i.e., all k-element subsets of {1,2,...,2k}, strengthening the classical Chung-Feller theorem. Balanced combinations are naturally represented by bitstrings of length 2k with exactly k many 1-bits, and thus encode a vast collection of Catalan-type objects such as Dyck paths, ordered trees, binary trees, triangulations

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010