Decision trees with minimum average depth for sorting eight elements

Hassan M. AbouEisha, Igor Chikalov, Mikhail Moshkov

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

We prove that the minimum average depth of a decision tree for sorting 8 pairwise different elements is equal to 620160/8!. We show also that each decision tree for sorting 8 elements, which has minimum average depth (the number of such trees is approximately equal to 8.548×10^326365), has also minimum depth. Both problems were considered by Knuth (1998). To obtain these results, we use tools based on extensions of dynamic programming which allow us to make sequential optimization of decision trees relative to depth and average depth, and to count the number of decision trees with minimum average depth.
Original languageEnglish (US)
Pages (from-to)203-207
Number of pages5
JournalDiscrete Applied Mathematics
Volume204
DOIs
StatePublished - Nov 19 2015

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Decision trees with minimum average depth for sorting eight elements'. Together they form a unique fingerprint.

Cite this