Designing an algorithm for a given problem is a difficult intellectual exercise. This is because there is no systematic method for designing an algorithm.
Moreover, there may be more than one algorithm to solve a given problem. Writing an effective algorithm for a new problem or writing a better algorithm for an already existing algorithm is art as well as science
because it requires both, creativity and insight.
Identifying Techniques for Designing Algorithms
Although there is no systematic method for designing an algorithm, there are some well-known techniques that have proved to be quite useful in designing algorithms.
The following two techniques are commonly used for designing algorithms:
- Divide and conquer approach
- Greedy approach
Divide and Conquer Approach
The divide and conquer approach is an algorithm design technique that involves breaking down a problem recursively into subproblems until the subproblems become so small and trivial that they can be easily solved.
The solutions to the subproblems are then combined to give a solution to the original problem. Divide and conquer is a powerful approach to solving conceptually difficult problems.
It simply requires you to find a way of breaking the problem into subproblems, solving the trivial cases, and combining the solutions to the subproblems to solve the original problem.
Divide and conquer often provides a natural way to design efficient algorithms. Consider an example where you have to find the minimum value in a list of numbers. The list of numbers is as shown in the following figure.
To find the minimum value, you can divide the list into two halves, as shown in the following figure.
Again, divide each of the two lists into two halves, as shown in the following figure.
Now, there are only two elements in each list. At this stage, compare the two elements in each list to find the minimum of the two. The minimum value from each of the four lists is shown in the following figure.
Again, compare the first two minimum values to determine their minimum. Also, compare the last two minimum values to determine their minimum.
The two minimum values thus obtained are shown in the following figure.
Again, compare the two final minimum values to obtain the overall minimum value, which is 1 in the preceding example.
The greedy approach is an algorithm design technique that selects the best possible option at a given time. Algorithms based on the greedy approach are used for solving optimization problems where you need to maximize profits or minimize costs under a given set of conditions.
Some examples of optimization problems are:
1. Finding the shortest distance from an originating city to a set of destination cities, given the distances between the pairs of cities.
2. Finding the minimum number of currency notes required for an amount, where an arbitrary number of notes for each denomination is available.
3. Selecting items with maximum value from a given set of items, where the total weight of the selected items cannot exceed a given value.
Consider an example where you have to fill a bag of capacity 10 kg by selecting items, (from a set of items) whose weights and values are given in the following table.
A greedy algorithm acts greedy, and therefore, selects the item with the maximum total value at each stage. Therefore, first of all, the item, C, with a total value of $800 and a weight of 4 kg will be selected. Next, the item, E, with a total value of $500 and weight of 5 kg will be selected.
The next item with the highest value is an item, B, with a total value of $450 and a weight of 3 kg. However, if this item is selected, the total weight of the selected items will be 12 kg (4 + 5 + 3), which is more than the capacity of the bag.
Therefore, we discard the item, B, and search for the item with the next higher value. The item with the next higher value is an item, A, which has a total value of $400 and a total weight of 2 kg.
However, this item also cannot be selected because if it is selected, the total
weight of the selected items will be 11 kg (4 + 5 + 2). Now, there is only one item left, that is, item, D, with a total value of $50 and a weight of 1 kg.
This item can be selected as it makes the total weight equal to 10 kg.
The selected items and their total values and weights are listed in the following table.
For most of the problems, the greedy algorithms usually fail to find the globally optimal solution. This is because they usually do not operate exhaustively on all data.
They can make commitments to certain choices too early. Hence, it prevents them from finding the best overall solution, later.
This can be seen from the preceding example where the use of a greedy algorithm selects the items with a total value of $1350 only. However, if the items were selected in the sequence depicted by the following table, the total the value would have been greater, with the weight being 10
In the preceding example, you can observe that the greedy approach commits to an item, E, very early. This prevents it from determining the best overall solution, later.
Nevertheless, the greedy approach is useful because it is quick and easy to implement. Moreover, it
often gives a good approximation to the optimal value.