TY - JOUR
T1 - Decision trees with minimum average depth for sorting eight elements
AU - AbouEisha, Hassan M.
AU - Chikalov, Igor
AU - Moshkov, Mikhail
N1 - KAUST Repository Item: Exported on 2020-10-01
PY - 2015/11/19
Y1 - 2015/11/19
N2 - 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.
AB - 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.
UR - http://hdl.handle.net/10754/583291
UR - http://linkinghub.elsevier.com/retrieve/pii/S0166218X1500517X
UR - http://www.scopus.com/inward/record.url?scp=84947460782&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2015.10.030
DO - 10.1016/j.dam.2015.10.030
M3 - Article
SN - 0166-218X
VL - 204
SP - 203
EP - 207
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -