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 gcd The 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 Treetree = 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 Traversaldef preorder(tree): if tree: print(tree.key) preorder(tree.left_child) preorder(tree.right_child) #In-order Traversaldef inorder(tree): if tree: inorder (tree.left_child) print(tree.key) inorder (tree.right_child) #Post-order Traversaldef 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 primedef 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 primesdef find_primes(N): primes = [] for i in range(2, N+1): if is_prime(i): primes.append(i) return primes This 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.
Recommended next reads
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_numbers
4. 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 result This 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 numberdef 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 b Are there any other algorithms in your mind that you find beautiful? Let me know in the comments below.
