2014

2015

2016

2017

2018

2019

2020

2022

2023

2024

The 59th meeting of the Prague computer science seminar

Stefan Edelkamp

Sorting and Searching for Algorithmic Intelligence

In the early days of computer science Donald E. Knuth and Kurt Mehlhorn both dedicated one book of their monographs to the topic of sorting and searching. During my research, I found some major algorithmic improvements to these fundamental problems documented in my new book on "Algorithmic Intelligence".

Annotation Lecturer Poster

2024
2023
2022
2020
2019
2018
2017
2016
2015
2014

Play record

April 18, 2024

4:15pm

Auditorium S5, MFF UK
Malostranské nám. 25, Praha 1
Show on the map

QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare’s Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like Heapsort, Insertionsort and Mergesort. Its major advantage is that QuickXsort can be in-place even if X is not. By doing so the mean number of comparisons can be reduced down to n*log(n) – 1.4112*n + o(n) for a remaining gap of only 0.0315*n comparisons to the lower bound.

On the practical side, BlockQuicksort beats standard library implementations and has been included in libcxx. I will also introduce a variant of a binary heap that operates in-place, executes minimum and insert in worst-case constant time, and extract-min in O(log(n)) worst-case time, while involving at most log(n) + O(1) element comparisons. These efficiencies surpass lower bounds known for standard binary heaps, thereby resolving a long-standing theoretical debate.

Stefan Edelkamp

Dr. Stefan Edelkamp is a professor at Charles University and Czech Technical University in Prague. Previously he was the leader of the planning group at King's College London and also worked at the Institute for Artificial Intelligence, Faculty of Computer Science and Mathematics of the University of Bremen, and at the University of Applied Science in Darmstadt. For a short period of time, he held the position of an Interim Professor at the University of Koblenz and Landau and Paris Dauphine University. He earned his Ph.D. from Freiburg University and led a junior research group at the Technical University of Dortmund. His main scientific interest is algorithmic intelligence, including heuristic search, action planning, game playing, machine learning, motion planning, multiagent simulation, model checking, distributed computing, algorithm engineering, and computational biology.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.