License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.2
URN: urn:nbn:de:0030-drops-120766
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12076/
Go to the corresponding LIPIcs Volume Portal

Edelkamp, Stefan

Algorithm Engineering for Sorting and Searching, and All That (Invited Talk)

pdf-format:
LIPIcs-SEA-2020-2.pdf (0.3 MB)

Abstract

We look at several proposals to engineer the set of fundamental searching and sorting algorithms. Aspects are improving locality of disk access and cache access, the efficiency tuning by reducing the number of branch mispredictions, and reducing at leading factors hidden in the Big-Oh notation. These studies in algorithm engineering, in turn, lead to exiting new algorithm designs. On the practical side, we will establish that efficient sorting and searching algorithms are in tight collaboration, as sorting is used for finding duplicates in disk-based search, and heap structures designed for efficient graph search can be exploited in classical and adaptive sorting. We indicate the effects of engineered sorting and searching for combined task and motion planning.

BibTeX - Entry

@InProceedings{edelkamp:LIPIcs:2020:12076,
  author =	{Stefan Edelkamp},
  title =	{{Algorithm Engineering for Sorting and Searching, and All That (Invited Talk)}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12076},
  URN =		{urn:nbn:de:0030-drops-120766},
  doi =		{10.4230/LIPIcs.SEA.2020.2},
  annote =	{Keywords: Sorting, Searching, Algorithm Engineering}
}

Keywords: Sorting, Searching, Algorithm Engineering
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI