Skip to main content

Questions tagged [towers-of-hanoi]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

Does a bijective function exists behind every recurrence relation?

Consider these 2 questions where recurrence relations can be applied: Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
rustlecho's user avatar
1 vote
1 answer

Tower of Hanoi variation - Split into two towers of odd and even disks

Suppose we have three rods A, B and C, and rod A ...
Daniel's user avatar
  • 119
1 vote
1 answer

Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$

I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my ...
Elliott de Launay's user avatar
4 votes
1 answer

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
gunnnnii's user avatar
3 votes
1 answer

Analysis of the Banana Game

My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs. Game Description The banana game is played with a ...
antonky's user avatar
  • 133
1 vote
4 answers

Towers of Hanoi First Move

I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below. However one thing still bugs me - I can't yet work out how this simple seeming ...
Robin Andrews's user avatar
1 vote
0 answers

Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs

Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of ...
neutron-byte's user avatar
1 vote
0 answers

Proof for Iterative Solution of Towers of Hanoi

user7952's user avatar
2 votes
0 answers

Complexity class of Towers of Hanoi problem

Given a problem List all steps to move n disks from rode 1 to rode 2. I guess you are familiar with Towers of Hanoi rules. I couldn't find a proper answer for the complexity class of this problem....
Y N's user avatar
  • 247
1 vote
2 answers

How do I approach inductive design problems with no information or context given?

As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given ...
Zimano's user avatar
  • 113
2 votes
1 answer

Computing a Sequence of People Entering and Leaving a Room

I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows. You start with an empty room and a group of n people waiting outside. At each step, ...
jroschen's user avatar
  • 123
1 vote
2 answers

Tower Of Hanoi Time Calculation

I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution. The setup is the standard Towers of Hanoi, except that moving the ...
arqam's user avatar
  • 123
11 votes
1 answer

Towers of Hanoi but with arbitrary initial and final configuration

Recently, I came across this problem, a variation of towers of hanoi. Problem statement: Consider the folowing variation of the well know problem Towers of Hanoi: We are given $n$ towers ...
Null's user avatar
  • 211
6 votes
1 answer

An Alternative Hanoi Tower problem

We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...). Now we want to move all $2n$ disks to tower $T_3$. If $T(p,q)$ is a recurrence relation of minimum ...
Parisa's user avatar
  • 121
20 votes
1 answer

Complexity of Towers of Hanoi

I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments. Is it in NP? Attempted answer: Suppose Peggy (prover) solves the problem & submits it ...
PKG's user avatar
  • 1,489