Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871951 | Discrete Applied Mathematics | 2016 | 5 Pages |
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Ã10326365), 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hassan AbouEisha, Igor Chikalov, Mikhail Moshkov,