In a broad sense, many algorithms approach problems in the same way. Thus, it is often convenient to classify them based on the approach they employ. One reason to classify algorithms is to gain an insight about an algorithm and understand its general approach. This can also give us ideas about how to look at similar problems for which we do not know algorithms. Of course, some algorithms defy classification, whereas others are based on a combination of approaches. This section presents some common approaches.
1. Randomized Algorithms
Randomized algorithms rely on the statistical properties of random numbers. One example of a randomized algorithm is quicksort.
Imagine an unsorted pile of cancelled checks by hand. In order to sort this pile we place the checks numbered less than or equal to what we may think is the median value in one pile, and in the other pile we place the checks numbered greater than this. Once we have the two piles, we divide each of them in the same manner and repeat the process until we end up with one check in every pile. At this point the checks are sorted.
2. Divide-and-conquer Algorithms
Divide-and-conquer algorithms revolve around 3 steps divide, conquer and combine. In the divide step, we divide the data into smaller, more manageable pieces. In the conquer step, we process each division by performing some operations on it. In the combine step, we recombine the processed divisions. An example of the divide-and- conquer algorithm is merge sort.
As before, imagine an unsorted pile of cancelled checks by hand. We begin by dividing the pile in half. Next, we divide each of the resulting two piles in half and continue this process until we end up with one check in every pile. Once all piles contain a single check, we merge the piles two by two so that each pile is a sorted combination of the two that were merged. Merging continues until we end up with one big pile again, at which point the checks are sorted.
3. Dynamic-programming solutions
Dynamic-programming solutions are similar to divide-and- conquer methods in that both solve problems by breaking larger problems into sub-problems whose results are later recombined. However, the approaches differ in how sub-problems are related. In divide-and-conquer algorithms, each sub-problem is independent of the others. Therefore we solve each sub-problem using recursion and combine its results with the results of other sub-problems. In dynamic- programming solutions, sub-problems are not independent of one another. A dynamic-programming solution is better than a divide-and- conquer approach because the latter approach will do more work than necessary, as shared sub-problems are solved more than once. However, if the sub-problems are independent and there is no repetition, using divide-and-conquer algorithms is much better than using dynamic-programming.
An example of dynamic-programming is finding the shortest path to reach a point from a vertex in a weighted graph.
4. Greedy Algorithms
Greedy algorithms make decisions that look best at the moment. In other words, they make decisions that are locally optimal in the hope that they will lead to globally optimal solutions. The greedy method extends the solution with the best possible decision at an algorithmic stage based on the current local optimum and the best decision made in a previous stage. It is not exhaustive, and does not give accurate answer to many problems. But when it works, it will be the fastest method.
One example of a greedy algorithm is Huffman coding, which is an algorithm for data compression.
5. Approximation Algorithms
Approximation algorithms are algorithms that do not compute optimal solutions; instead, they compute solutions that are “good enough”. Often we use approximation algorithms to solve problems that are computationally expensive but are too significant to give up altogether. The travelling salesman problem is one example of a problem usually solved using an approximation algorithm.
