3

Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg. Recursive algorithm If $n > 1$, recursively move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, recursively move $n-1$ discs from B to C. Iterative algorithm If $n$ is ...


3

Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming. The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other ...


3

Starting from this system: $$ \begin{cases} T(1) = 1 \\ T(n) = 2T(n-1) + n \end{cases} $$ To use repertoire method to solve the system, we'll generalize it as this: $$ \begin{cases} T(1) = \alpha \\ T(n) = 2T(n-1) + \beta n + \gamma \end{cases} \tag 0 $$ The result must look like this: $$ T(n) = A(n) \alpha + B(n) \beta + C(n) \gamma $$ I. Let's try ...


2

Hint. Set up a recurrence relation similar to the one for the standard Towers of Hanoi. Then use the techniques from our reference question on recurrence relations to solve the recurrence.


2

The most succesful approach to deal with the original version of the Towers of Hanoi is using Pattern Databases (PDBs). The current state of the art is described in "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem" Pattern Databases are an automated means for deriving admissible heuristics which are necessary in ...


2

It seems to me that your teacher wants a induction proof where the induction is on the length of the array. It seems weird that your teacher does not provide a sorting algorithm . If the task is to sort an array, I would assume that your teacher is looking for an, as you say, arbitrary sorting algorithm and prove it with that. But if the teacher means that ...


2

Most questions in AI textbooks of this style are intended to be open ended so that the student can experiment on its own with the problem. So the golden rule is do as you see fit to provide the best learning! In particular for this problem, your approach seems appropriate. Since most sorting algorithms fall into a divide and conquer schema, you won't have ...


2

If you trace the recursion calls that your algorithm makes before it prints its first line, you will have if the first call is hanoi(n, 'A', 'B', 'C') : hanoi(n, 'A', 'B', 'C') hanoi(n-1, 'A', 'C', 'B') hanoi(n-2, 'A', 'B', 'C') ... hanoi(1, 'A', $ , €) Moving disc from A to $ To see if $ is equal to B or C, you just have to remark that the value of ...


1

If $n\lt k$, we have $T_k(n)=2n-1$. Let us focus on the remaining case, i.e, assuming $n\ge k$. One of the recurrence relations is, $$\quad T_k(n) =6+T_{k-1}(n-2)\ \ \text{for all }n\ge k\ge\frac {n+3}2\text{ and }n\ge3, $$ where $6$ comes from $2T_k(2)$, since $T_k(2)=3$. Applying the recurrence relation above repeatedly, we have $$\begin{align} T_k(n)&...


1

The broad idea behind solving Tower of Hanoi problem by recursion is this: The whole stack of n disks needs to be transferred to the to pole from from pole. Imagine there are n disks (instead of 3 shown) on the from pole. The idea behind recursive solution is to consider the top $n-1$ disks as a single combined disk, transfer this combined disk to using pole,...


1

The first move is produced by the first recursive call in the code, which is repeatedly invoked many times, until the base case is reached -- printing the first move. We note that hanoi(n, from_peg, to_peg, spare_peg) makes as its first recursive call hanoi(n-1, from_peg, spare_peg, to_peg), so this swaps the last two arguments, and decreases n. Hence, the ...


1

Base case It's easy to generate the combinations when $n=1$: just use the operation $e_1$. Recursion Now assume that you have a sequence $ops_n$ that will generate all the combinations of $n$ people. Define $rops_n$ to be the sequence of operations that "undoes" $ops_n$, namely first form the reverse of $ops_n$ and then replace all "enter" operations with "...


Only top voted, non community-wiki answers of a minimum length are eligible