There are five types of algorithms in Python: 1. Recursive Algorithms, 2. Memoization Algorithms, 3. Divide and Conquer Algorithms, 4. Dynamic Programming Algorithms, 5. Greedy Algorithms
1. Recursive Algorithms
What is Recursive Algorithms?
A recursive algorithm is an algorithm which calls itself with a smaller or simpler input each time. Eventually, the input becomes so small or simple that the algorithm can return a direct answer.
What are the usages of Recursive Algorithms?
There are many uses for recursive algorithms, including:
- Finding the factorial of a number
- Computing the Fibonacci sequence
- Generating permutations and combinations
- Solving Towers of Hanoi puzzles
- Searching and sorting data structures
- Implementing certain mathematical functions
- Manipulating directory trees and file systems
Features of Recursive Algorithm:
- Recursive algorithms are easy to understand and implement.
- Recursive algorithms can play an important role in solving complex problems.
- Recursive algorithms can be used to obtain an optimal solution to a problem.
- Recursive algorithms can be used to generate efficient code.
Examples of Recursive Algorithm:
-Traversing a tree or a graph
def traverse(node, visited):
visited[node] = True
print(node, end=" ")
for i in graph[node]:
if visited[i] == False:
traverse(i, visited)-Calculating the factorial of a number
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)-Generating all permutations of a set of elements
def permutations(elements):
if len(elements) <= 1:
yield elements
else:
for perm in permutations(elements[1:]):
for i in range(len(elements)):
yield perm[:i] + elements[0:1] + perm[i:]2. Memoization Algorithms
What is Memoization Algorithm?
Memoization is an optimization technique used to speed up programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
What are usages of Memoization Algorithms?
Memoization algorithms are used to optimize code by storing the results of expensive function calls and reusing the results when the same inputs occur again. This can improve the performance of the code by reducing the number of expensive function calls that need to be made.
Features of Memoization Algorithms:
- The speed of execution is increased.
- It reduces the space complexity.
- It avoids duplicate computations.
- It improves the code readability.
- It is easy to implement.
- It is applicable to both serial and parallel programs.
- It is highly flexible and can be easily customized.
Examples of Memoization Algorithms:
* Fibonacci series
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)* Factorial
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)* Matrix Exponentiation
def matrix_exponentiation(A, n):
if n == 1:
return A
if n % 2 == 0:
return matrix_exponentiation(matrix_multiply(A, A), n // 2)
else:
return matrix_multiply(A, matrix_exponentiation(A, n - 1))* Longest Common Subsequence (LCS)
def lcs(X, Y, m, n):
if m == 0 or n == 0:
return 0
elif X[m - 1] == Y[n - 1]:
return 1 + lcs(X, Y, m - 1, n - 1)
else:
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n))* Shortest Path in a Directed Acyclic Graph (DAG)
def dag(graph, A, B):
# create a set of visited nodes
visited = set()
# create a set of nodes to be visited
unvisited = set(graph.keys())
# create a dictionary of distances
distance = {}
# create a dictionary of predecessors
predecessor = {}
# assign the distance from A to A to be 0
distance[A] = 0
# assign the predecessor of A to be None
predecessor[A] = None
# while there are unvisited nodes
while unvisited:
# find the node with the smallest distance in the set of unvisited nodes
current = min(unvisited, key=lambda k: distance[k])
# remove the node from the set of unvisited nodes
unvisited.remove(current)
# if the distance of the current node is infinity, there is no path to the end node
if distance[current] == float('inf'):
break
# for each neighbor of the current node
for neighbor in graph[current]:
# if the neighbor is not visited
if neighbor not in visited:
# if the distance to the neighbor is greater than the distance to the current node plus the edge weight
if distance[neighbor] > distance[current] + graph[current][neighbor]:
# update the distance to the neighbor
distance[neighbor] = distance[current] + graph[current][neighbor]
# update the predecessor of the neighbor
predecessor[neighbor] = current
# add the current node to the set of visited nodes
visited.add(current)
# if the distance to the end node is infinity, there is no path to the end node
if distance[B] == float('inf'):
return None
# create a list of nodes that are on the shortest path from the start node to the end node
path = []
# set the current node to be the end node
current = B
# while the current node has a predecessor
while current:
# add the current node to the list of nodes
path.append(current)
3. Divide and Conquer Algorithms
What are Divide and Conquer Algorithms?
Divide and conquer algorithms are designed to facilitate efficient execution of a given task by breaking it down into smaller, more manageable sub tasks. These sub tasks are then solved independently, with the overall solution being obtained by combining the solutions to the sub tasks. A typical example of a divide and conquer algorithm is the quicksort algorithm, which is used to sort an array of data.
What are the usages of Divide and Conquer Algorithms?
There are many usage cases for divide and conquer algorithms. Some common applications include:
- searching and sorting data sets
- multiplying large numbers
- solving complex mathematical problems
- finding the shortest path between two points
Features of of Divide and Conquer Algorithms:
Some features of divide and conquer algorithms include their ability to solve problems recursively, their use of subproblems, and their generally efficient running time. Additionally, divide and conquer algorithms often have a good worst-case performance guarantee.
Examples of of Divide and Conquer Algorithms:
Here are a few examples of divide and conquer algorithms:
1. Merge sort
Click here to go to Merge Sort
2. Quick sort
Click here to go to Quick Sort
3. Binary search
Click here to go to Binary search
4. Strassen’s matrix multiplication
def strassen_matrix_multiply(A, B):
# A and B are two matrices
# A[i][j] is the i-th row and j-th column of A
# B[i][j] is the i-th row and j-th column of B
# C[i][j] is the i-th row and j-th column of C
# C = A * B
# n is the dimension of the matrices
n = len(A)
# base case
if n == 1:
return [[A[0][0] * B[0][0]]]
# split the matrices into 4 sub-matrices
# A11 A12
# A21 A22
# B11 B12
# B21 B22
# C11 C12 C21 C22
# n/2 is the dimension of the sub-matrices
A11 = [[A[i][j] for j in range(n // 2)] for i in range(n // 2)]
A12 = [[A[i][j] for j in range(n // 2, n)] for i in range(n // 2)]
A21 = [[A[i][j] for j in range(n // 2)] for i in range(n // 2, n)]
A22 = [[A[i][j] for j in range(n // 2, n)] for i in range(n // 2, n)]
B11 = [[B[i][j] for j in range(n // 2)] for i in range(n // 2)]
B12 = [[B[i][j] for j in range(n // 2, n)] for i in range(n // 2)]
B21 = [[B[i][j] for j in range(n // 2)] for i in range(n // 2, n)]
B22 = [[B[i][j] for j in range(n // 2, n)] for i in range(n // 2, n)]
# calculate the sub-matrices of C
# C11 = A11*B11 + A12*B214. Dynamic Programming Algorithms
What is Dynamic Programming Algorithm?
A dynamic programming algorithm is an algorithm that solves a complex problem by breaking it down into smaller subproblems. It then solves each subproblem using a bottom-up approach, and finally combines the solutions to the subproblems to solve the original problem.
What are the usages of Dynamic Programming Algorithms?
These algorithms typically have a recursive structure, and they use memoization to store the results of previous computations to avoid re-computing the same subproblem multiple times. The one usage of Dynamic Programming Algorithm is to find the shortest path between two nodes in a graph.
Examples of Dynamic Programming Algorithms:
Maximum Subarray:
Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
def maxSubArray(nums):
if len(nums) == 0:
return 0
max_sum = nums[0]
curr_sum = nums[0]
for i in range(1, len(nums)):
curr_sum = max(nums[i], curr_sum + nums[i])
max_sum = max(max_sum, curr_sum)
return max_sumknapsack problem:
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
def knapsack(W, wt, val, n):
K = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]5. Greedy Algorithms
What are Greedy Algorithms?
A greedy algorithms is one that always chooses the best option available at each step, without regard for future consequences.
What are the usages of Greedy Algorithms?
Greedy algorithms are often used for optimization problems. An optimization problem is one where we want to find the best solution from a set of possible solutions. Greedy algorithms work by making the best choice at each step, without regard for future consequences. This can often lead to sub-optimal solutions, but greedy algorithms are usually much faster than other algorithms that guaranteed to find the optimal solution.
Features of Greedy Algorithms:
Some key features of greedy algorithms include:
- They are simple and easy to implement.
- They are usually efficient in terms of time and space.
- They can be used to solve a wide variety of problems.
- They often produce near-optimal solutions.
Examples of Greedy Algorithms:
1) Huffman coding
Huffman coding is a method of encoding characters based on their frequency. The process of finding the optimal prefix codes for characters is called Huffmandef HuffmanCoding(data):
def HuffmanCoding(data):
# data is a list of tuples (char, frequency)
# return a list of tuples (char, encoding)
# build a heap
heap = []
for char, freq in data:
heapq.heappush(heap, (freq, char))
# build a tree
while len(heap) > 1:
freq1, char1 = heapq.heappop(heap)
freq2, char2 = heapq.heappop(heap)
heapq.heappush(heap, (freq1 + freq2, (char1, char2)))
# build a code
code = {}
def build_code(tree, prefix):
if isinstance(tree, str):
code[tree] = prefix
else:
build_code(tree[0], prefix + '0')
build_code(tree[1], prefix + '1')
build_code(heap[0][1], '')
return code2) Kruskal’s algorithm
def kruskal(vertices, edges):
# sort the edges in non-decreasing order of their weight
edges = sorted(edges, key=lambda x: x[2])
# create a disjoint set data structure
ds = DisjointSet(vertices)
# create a list to store the minimum spanning tree
mst = []
# start from the first edge in the sorted edges
for edge in edges:
# get the two vertices of the current edge
u, v, w = edge
# if the two vertices of the current edge are in different trees
if ds.find(u) != ds.find(v):
# add the current edge to the MST
mst.append(edge)
# merge the two trees
ds.union(u, v)
# return the MST
return mstOR
# to find the minimum spanning tree of a graph
# using the union-find data structure
def kruskal(graph):
# sort the edges in non-decreasing order
# by weight
edges = sorted(graph['edges'], key=lambda x: x[2])
# initialize the disjoint set forest
# which will store the vertices
# and their parent/child relationship
forest = DisjointSetForest(graph['vertices'])
# initialize the minimum spanning tree
# which will store the edges
# and their weight
mst = []
# loop over the sorted edges
for edge in edges:
# get the indices of the edge's
# endpoints
u, v, w = edge
# if the endpoints
# are in different components
if forest.find(u) != forest.find(v):
# add the edge to the mst
mst.append(edge)
# merge the components
# of the endpoints
forest.union(u, v)
# return the edges in the mst
return mst3) Prim’s algorithm
def prim(graph, start):
# create a list of nodes
nodes = []
# create a list of edges
edges = []
# create a list of nodes
for node in graph:
nodes.append(node)
# create a list of edges
for edge in graph:
edges.append(edge)
# create a list of distances
distances = [float("inf")] * len(nodes)
# create a list of previous nodes
previous = [None] * len(nodes)
# set the distance of the start node to 0
distances[start] = 0
# while there are still nodes to visit
while len(nodes) > 0:
# find the node with the smallest distance
smallest = None
for node in nodes:
if smallest is None:
smallest = node
elif distances[node] < distances[smallest]:
smallest = node
# remove the smallest node from the nodes list
nodes.remove(smallest)
# find the neighbors of the smallest node
neighbors = []
for edge in edges:
if edge[0] == smallest:
neighbors.append(edge[1])
elif edge[1] == smallest:
neighbors.append(edge[0])
# find the neighbor with the smallest distance
for neighbor in neighbors:
if neighbor in nodes:
if distances[neighbor] > distances[smallest] + graph[(smallest, neighbor)]:
distances[neighbor] = distances[smallest] + graph[(smallest, neighbor)]
previous[neighbor] = smallest
# return the list of distances and the list of previous nodes
return distances, previous4) Dijkstra’s algorithm
For further explaination regarding Dijkstra Algorithm, click here
def dijkstra(graph, start, end):
# keep track of all the nodes that have been visited
nodes = set()
# keep track of all the paths to be checked
paths = [[start, 0]]
# shortest path dictionary
shortest_path = {}
# while there is still a path to be checked
while paths:
# sort the paths by their weight
paths = sorted(paths, key=lambda x: x[1])
# get the first path
path = paths.pop(0)
# get the last node from the path
node = path[-1]
# check if the node has already been visited
if node not in nodes:
# add the node to the visited nodes
nodes.add(node)
# check if the node is the end node
if node == end:
# set the shortest path to the path found
shortest_path = path
else:
# loop through the neighbors of the node
for neighbor, distance in graph[node].items():
# create a new path to the neighbor with the distance
new_path = list(path)
new_path.append(neighbor)
new_path.append(distance)
# add the new path to the paths to be checked
paths.append(new_path)
# return the shortest path
return shortest_path5) Knapsack problem
def knapsack(W, wt, val, n):
K = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]