The Science of Computing II: Living with Cyber Recursion Study Notes

The Science of Computing II: Living with Cyber Recursion

Pillar: Algorithms

The Towers of Hanoi

The Towers of Hanoi is a classic puzzle consisting of three pegs (or towers) and several discs of varying sizes. The objective of the game is to move all the discs from a source tower to a destination tower while adhering to specific rules:

1. Only one disc may be moved at a time.

2. No larger disc may be placed on top of a smaller disc.

3. Moving a single disc counts as one move.

Gameplay

Initially, all discs rest on a single source tower, with the largest disc at the bottom and the smallest at the top. The goal is to achieve this transfer with the minimum number of moves possible.

Optimization Problem

The Towers of Hanoi is an optimization problem, not just a problem of finding any solution. The focus is to find the optimal solution that requires the least moves. For instance, while one could occasionally arrive at a solution in, say, 100 moves, the minimum number of moves required to solve the Towers of Hanoi with three discs is actually seven.

Moves for Three Discs

Here is the sequence of moves to achieve this:

1. Move disc 1 from the source tower to the destination tower.

2. Move disc 2 from the source tower to the spare tower.

3. Move disc 1 from the destination tower to the spare tower.

4. Move disc 3 from the source tower to the destination tower.

5. Move disc 1 from the spare tower to the source tower.

6. Move disc 2 from the spare tower to the destination tower.

7. Move disc 1 from the source tower to the destination tower.

Minimum Moves Required

A pattern emerges when considering the minimum number of moves required for different numbers of discs. The table below summarizes this:

General Case for n Discs

For a general case with n discs, the minimum number of moves required can be represented by the formula:
$2^n - 1$
This is observed as follows:

• For one disc: $2^1 - 1 = 1$

• For two discs: $2^2 - 1 = 3$

• For three discs: $2^3 - 1 = 7$

The pattern indicates that with each additional disc, the minimum moves double plus one. The generalized formula can be expressed as:
$M(n) = 2^n - 1$ where M(n) represents the minimum number of moves for n discs.

Time to Solve the Puzzle

Assuming each move takes 1 second, it would take:

• Approximately 63 seconds to complete the puzzle with six discs (63 moves).

• About two minutes for seven discs (127 moves).

• Approximately 16 minutes for ten discs (1023 moves).

• Roughly 11 days for twenty discs (1,048,575 moves).

If one has access to a computational power that can perform 500 million moves per second, estimates show:

• About 2 seconds for thirty discs.

• Around 4 seconds for thirty-one discs.

• Roughly 1 minute for thirty-five discs.

• Nearly a month for fifty discs!

Ethereal Implications

There exists a narrative that a group of monks is endeavoring to solve the Towers of Hanoi with 64 golden discs, believing their work will herald the end of the world. They are said to take ten minutes for each move which would result in over 350 billion millennia to complete the puzzle, derived from the immense computational complexity involved (18.4 quintillion moves).

Breaking Problems Down

Consider the use of algorithms to address simpler combinatorial problems, like forming pairs from a group:

Grouping Students

Given 10 students, how many unique pairs of two can be made?

Initial Cases

1. Two Students: There is only one way (S1, S2).

2. Three Students: The pairs are S1 and S2; S1 and S3; S2 and S3, providing three unique combinations.

3. Four Students: The possible pairs total six:

   • S1, S2

   • S1, S3

   • S1, S4

   • S2, S3

   • S2, S4

   • S3, S4

4. Five Students: The result yields ten unique pairs.

Recurrence Relation

The number of unique pairings demonstrates a pattern: it can be derived from summation of the previous counts of pairings. For instance, the count for four students yields 6:

• Groups[4] = Groups[3] + [3], incrementally adding combinations as students are added.

Establishing G(n)

The general recurrence relation for the number of groups of two from n students is:
G(n) = egin{cases}
0 & ext{if } n = 1 \
G(n-1) + (n-1) & ext{otherwise}
\end{cases}
Where:

• G(n) denotes the number of groups from n total students.

Definition of Recurrence Relation

A recurrence relation is defined as an equation that recursively defines a sequence. In the above, each term corresponds to the previous values leading to the computation of G. The base case, G(1) = 0, shows that no pairs can be formed from a single student.

Divide and Conquer Algorithms

These algorithms often apply recurrence relations, systematically breaking down tasks until a base case is reached, subsequently building solutions back up.

Recursion in Programming

Recursion represents a function or a program repeating itself until reaching a base or trivial case. This necessitates:

1. A base case yielding an immediate answer.

2. A recursive step formalizing how the problem reduces in scale.

Example: Calculating Power

For a power calculation, the recursive definition is:
ext{Pow}(x, y) = egin{cases}
1 & ext{if } y = 0 \
x * ext{Pow}(x, y-1) & ext{otherwise}
\end{cases}

The power of two can be recursively reduced and calculated example:
$2^{10}$
Yields an output of 1024 using repeated multiplication recursively.

Factorial Function

The factorial function exemplifies recursion:
ext{Fact}(n) = egin{cases}
1 & ext{if } n=0 \
n * ext{Fact}(n-1) & ext{otherwise}
\end{cases}

For example, to compute $5!$, the recursive implementation calls and sums elements down to the base case.

Fibonacci Sequence

The Fibonacci sequence can also be defined recursively:
ext{Fib}(n) = egin{cases}
0 & ext{if } n=1 \
1 & ext{if } n=2 \
ext{Fib}(n-1) + ext{Fib}(n-2) & ext{otherwise}
\end{cases}
The recursive structure branches down calculating two preceding terms.

Recursive Solutions: Towers of Hanoi Revisited

Using recursion for the Towers of Hanoi, we can discern the three algorithmic components for n discs as:

1. Move n - 1 discs from source to spare.

2. Move the largest disc from source to destination.

3. Move n - 1 discs from spare to destination.

Algorithm Implementation in Python

The recursive algorithm can be defined in Python as:

def hanoi(n, src, dst, spr):
    if n == 1:
        print("{} -> {}".format(src, dst))
    else:
        hanoi(n - 1, src, spr, dst)
        hanoi(1, src, dst, spr)
        hanoi(n - 1, spr, dst, src)

This presents versatility to solve the Towers of Hanoi problem efficiently, leading to a structured theoretical understanding of recursion and algorithms.