Divide and Conquer Algorithm

Hanota Tower

The Hanota Tower, also known as the Tower of Hanoi, is a mathematical puzzle that consists of three rods and a number of disks of different sizes. The objective is to move the entire stack of disks from one rod to another, following these rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a smaller disk.

python implementation of the Hanota Tower problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def hanota(n, source, target, auxiliary):
    if n == 1:
        hanota(1, source, target, auxiliary)
        print(f"Move disk 1 from {source} to {target}")
        return

    hanota(n - 1, source, auxiliary, target)
    hanota(1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    hanota(n - 1, auxiliary, target, source)

# Example usage:
n = 3  # Number of disks
hanota(n, 'A', 'C', 'B')  # A is the source rod, C is the target rod, B is the auxiliary rod

Karatsuba Multiplication

Karatsuba multiplication is an efficient algorithm for multiplying large numbers. It reduces the multiplication of two n-digit numbers to at most three multiplications of n/2-digit numbers, which is faster than the traditional O(n^2) algorithm.

Here is the implementation of Karatsuba multiplication in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y

    max_len = max(len(str(x)), len(str(y)))
    half_len = max_len // 2

    x_high = x // 10**half_len
    x_low = x % 10**half_len
    y_high = y // 10**half_len
    y_low = y % 10**half_len

    z0 = karatsuba(x_low, y_low)
    z1 = karatsuba((x_low + x_high), (y_low + y_high))
    z2 = karatsuba(x_high, y_high)

    return (z2 * 10**(2 * half_len)) + ((z1 - z2 - z0) * 10**half_len) + z0
# Example usage:
x = 1234
y = 5678
result = karatsuba(x, y)
print(f"The product of {x} and {y} is: {result}")