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.FUN.2016.5
URN: urn:nbn:de:0030-drops-58729
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5872/
Go to the corresponding LIPIcs Volume Portal

Barbay, Jérémy

Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time

pdf-format:
12.pdf (0.6 MB)

Abstract

The Hanoi Tower problem is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound correspond to the solution of a simple recursive function (the solution is so simple that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some minor change in the rules of the Hanoi Tower yields various increases of difficulty in the solution, so that to require a deeper mastery of recursion than the classical Hanoi Tower problem. In particular, we analyze the Selenite Tower problem, where just changing the insertion and extraction positions from the top to the middle of the tower results in a surprising increase in the intricacy of the solution: such a tower of n disks can be optimally moved in 3^(n/2) moves for n even (i.e. less than a Hanoi Tower of same height), via 5 recursive functions (or, equivalently, one recursion function with five states following three distinct patterns).

BibTeX - Entry

@InProceedings{barbay:LIPIcs:2016:5872,
  author =	{J{\'e}r{\'e}my Barbay},
  title =	{{Selenite Towers Move Faster Than Hanoi Towers, But Still Require Exponential Time}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Erik D. Demaine and Fabrizio Grandoni},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5872},
  URN =		{urn:nbn:de:0030-drops-58729},
  doi =		{10.4230/LIPIcs.FUN.2016.5},
  annote =	{Keywords: Br{\"a}hma tower, Disk Pile, Hanoi Tower, Levitating Tower, Recursivity}
}

Keywords: Brähma tower, Disk Pile, Hanoi Tower, Levitating Tower, Recursivity
Collection: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 02.06.2016

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