April 18, 2024

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".

Quick*X*sort 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 Quick*X*sort 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.

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.

Prague computer science seminar is suspended until further notice to prevent spread of the new coronavirus.