Some Algorithms Are Just Beautiful. Don’t Believe Me? Read This!
Euclid’s Algorithm, The Sieve of Eratosthenes (& more)
I’ll be honest, starting to learn about Data Structures & Algorithms was mind-bogglingly tough.
However, the more I persisted, the more I discovered some algorithms that I could only describe as ‘beautiful’.
Here are 5 of those algorithms.
1. Euclid’s Algorithm
Amateur Approach
When trying to compute the greatest common divisor of two integers, the amateur I would have taken the following steps.
def find_gcd(x, y):
gcd = 1
min_num = min(x, y)
for i in range(1, min_num + 1):
if x % i == 0 and y % i == 0:
gcd = i
return gcdThe above function iterates through all the numbers from 1 up to the smaller of the two given integers.
For each number i, it checks if both given integers are divisible by i. If this is the case, this number is returned as a result.
The Beautiful Algorithm
Here comes the Euclid’s Algorithm.
This algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers.
The algorithm is based on the principle that the GCD of two numbers also divides their difference.
Here is how it looks.
def euclid_algorithm(x, y):
return x if y == 0 else euclid_algorithm(y, x % y)The algorithm recursively substitutes the larger numbers with the remainder of their division and terminates when the second number becomes 0 , returning the first number as the GCD.
2. Depth First Tree Traversal
Let’s write a Binary tree to begin with.
class BinaryTree:
def __init__(self, value):
self.key = value
self.left_child = None
self.right_child = None
def insert_left(self, value):
if self.left_child == None:
self.left_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.left_child = self.left_child
self.left_child = bin_tree
def insert_right(self, value):
if self.right_child == None:
self.right_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.right_child = self.right_child
self.right_child = bin_tree# Creating a new Binary Tree
tree = BinaryTree(1)
tree.insert_left(2)
tree.insert_right(3)
tree.insert_left(4)
tree.left_child.insert_right(6)
tree.insert_right(5)The binary tree looks like this:
1
/ \
4 5
/ \
2 3
\
6 Here are the elegant algorithms for traversing through this tree, depth-first.
#Pre-order Traversal
def preorder(tree):
if tree:
print(tree.key)
preorder(tree.left_child)
preorder(tree.right_child)#In-order Traversal
def inorder(tree):
if tree:
inorder (tree.left_child)
print(tree.key)
inorder (tree.right_child)#Post-order Traversal
def postorder(tree):
if tree:
postorder(tree.left_child)
postorder(tree.right_child)
print(tree.key)3. Sieve of Eratosthenes
Amateur Approach
The beginner’s approach to finding primes up to a certain limit N looks like the following.
# Function to check if a number is prime
def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True# Function to find primes
def find_primes(N):
primes = []
for i in range(2, N+1):
if is_prime(i):
primes.append(i)
return primesThis function performs a lot of unnecessary checks and thus is computationally expensive.
The Beautiful Algorithm
The Sieve of Eratosthenes is an old algorithm used to find all prime numbers up to the given limit.
The algorithm first creates a list from 2 up to the given limit and marks all numbers to be prime.
Then starting from the first prime number 2, it iteratively finds prime numbers and marks the multiples of the found prime numbers as non-prime.
This process continues till the square root of the given limit.
The numbers that remain unmarked are returned as the result.
def sieve_of_eratosthenes(limit):
prime = [True] * (limit + 1)
p = 2
while (p * p <= limit):
if prime[p] == True:
for i in range(p * p, limit + 1, p):
prime[i] = False
p += 1
prime_numbers = [p for p in range(2, limit) if prime[p]]
return prime_numbers4. Calculating Factorials
The iterative approach to finding factorials works as follows.
def factorial(n):
if n == 0:
return 1
result = 1
for i in range(1, n + 1):
result *= i
return resultThis method iteratively multiplies numbers from 1 up to n in a loop, accumulating the result.
I find the recursive approach quite elegant to code (although the approach is inefficient due to the recursive calls involved).
This is how it looks.
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1) 5. Generating Fibonacci Numbers
The recursive approach to generating Fibonacci numbers looks quite elegant again! (although it is inefficient for large values of n due to growing recursive calls).
# To calculate the nth Fibonacci number
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)The iterative approach for the same looks as follows.
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bAre there any other algorithms in your mind that you find beautiful? Let me know in the comments below.
