Python Data Structures: Algorithm Classes

An algorithm is a well-defined procedure that should produce a well-defined output by processing zero or more inputs. This leads to many approaches to designing and writing algorithms. It can be observed that most algorithms can be categorized into the following categories.

Greedy Algorithms

Greedy algorithms attempt to find a local optimal solution, which may eventually lead to a globally optimal solution. However, in general, greedy algorithms do not provide a globally optimal solution.

Thus, greedy algorithms search for an easy solution at that point in time without considering its impact on future steps. This is similar to how humans solve problems without fully understanding the details of the inputs provided.

Most network algorithms use a greedy approach. Here are a few of them –

• Traveling Salesman Problem

• Prim’s Minimum Spanning Tree Algorithm

• Kruskal’s Minimum Spanning Tree Algorithm

• Dijkstra’s Minimum Spanning Tree Algorithm

Divide and Conquer

This type of algorithm involves dividing a given problem into smaller subproblems and then solving each subproblem independently. When the problem cannot be further divided, we begin combining the solutions to each subproblem to arrive at a solution to the larger problem.

Important examples of divide and conquer algorithms include

• Merge sort

• Quick sort

• Kruskal’s minimum spanning tree algorithm

• Binary search

Dynamic Programming

Dynamic programming involves breaking a large problem into smaller ones, but unlike divide and conquer, it does not involve solving each subproblem independently. Instead, the results of smaller subproblems are remembered and used for similar or overlapping subproblems.

Most often, these algorithms are used for optimization. Dynamic algorithms attempt to examine the results of previously solved subproblems before solving the subproblem at hand. Dynamic algorithms are motivated by the goal of optimizing the entire problem, rather than local optimization.

Important examples of dynamic programming algorithms include

• Fibonacci sequence

• Knapsack problem

• Tower of Hanoi