Algorithm Classification¶
Classifying computing algorithms is a crucial task in computer science and mathematics, as it helps us understand and organize the vast array of algorithms used in various computational problems. Algorithms can be classified based on several criteria, allowing us to group them into categories that share common characteristics or problem-solving approaches. These classifications help researchers, programmers, and engineers select the most appropriate algorithm for a particular problem or optimize existing algorithms for better performance. In this introduction, we’ll explore some common methods for classifying computing algorithms.
By Design Paradigm¶
Design paradigms are also known as algorithmic paradigms. They are fundamental approaches, strategies, or methodologies used in the design of algorithms. They describe how an algorithm is designed, while problem types describe what output is requested. A paradigm is not tied to one problem type: its fit depends on the problem structure, the required output, and whether an exact or approximate answer is acceptable.
Brute force:
Brute-force algorithms solve problems by exhaustively searching through all possible solutions without exploiting any problem structure or patterns. They are simple to implement and are guaranteed to find a solution if it exists, but they are often computationally expensive and impractical for real-world problems.
Divide and Conquer:
This paradigm involves breaking down a complex problem into smaller, more manageable subproblems, solving them independently, and then combining their solutions to obtain the final result. The merge sort and quick sort algorithms are classic examples of divide-and-conquer algorithms.
Greedy Algorithms:
Greedy algorithms make locally optimal choices at each step. They solve a given problem exactly only when a greedy-choice argument applies; otherwise they may provide a heuristic or approximation. They are often used for optimization, such as minimum spanning tree algorithms.
Dynamic Programming:
Dynamic programming reuses results for overlapping subproblems (typically with optimal substructure). Depending on the recurrence, it can compute an optimum, a count, a yes/no answer, or another value; it does not necessarily list all solutions. Examples include Fibonacci numbers and knapsack.
Backtracking:
Backtracking is a technique used to solve problems incrementally by trying out different possibilities and undoing them if they don’t lead to a valid solution. It is commonly used in problems like the N-Queens problem and Sudoku solving.
Branch and Bound:
This paradigm explores a tree of partial candidates and uses bounds to prune branches that cannot improve the incumbent. It is commonly used for exact optimization, and can also answer related decision or search questions. The traveling salesman problem can be solved using branch and bound.
By Implementation Method¶
Recursive Algorithms: Algorithms that call themselves repeatedly until a base case is reached.
Iterative Algorithms: Algorithms that use loops to repeat a process until a condition is met.
Serial Algorithms: Algorithms that execute instructions sequentially on a single processor.
Parallel Algorithms: Algorithms that divide tasks among multiple processors or cores for simultaneous execution.
Distributed Algorithms: Algorithms that coordinate multiple computers or nodes in a network to solve a problem.
By Data Structure¶
Array
Linked List
Tree
Graph
By Application Domain¶
Sorting
Searching
String Processing
Computational Geometry
Numerical Algorithms
Optimization Algorithms
Machine Learning Algorithms
By Complexity Class¶
Polynomial Time
Exponential Time
NP-hard
By Specific Techniques Employed in the Algorithm¶
Randomized Algorithms
By Other Characteristics¶
Exact Algorithms: Guarantee the optimal solution
Approximation Algorithms: Find a solution that is close to the optimal solution
Deterministic algorithms: Always produce the same output for a given input
Non-deterministic algorithms: May produce different outputs for the same input
Heuristic Algorithms and Metaheuristics: Employ a set of rules or strategies to find a solution that is good enough