6 Design of Algorithms
T.V. Geetha
In this module we will discuss the various algorithm design techniques. We will explain these techniques using some illustrative examples.
Learning Objectives
The learning objectives of this module are as follows:
• To understand the different algorithm design techniques
• To know the type of problem that can be solved with different design techniques
• To take the same problem and explain how it can be solved using two techniques
6.1 Algorithm Design Technique
Algorithm design technique is a specific approach to create a design process for solving problems. These techniques can be applied to different computing problems. These general techniques provide guidelines for designing algorithms for new problems and to represent an useful collection of tools. Before we proceed further let us list out some generally used techniques.
Commonly used Techniques
• Brute force
• Decrease and Conquer
• Divide and Conquer
• Transform and Conquer
• Greedy Techniques
• Dynamic programming
• Backtracking
• Genetic Techniques
In this module we will discuss some of these techniques trying to bring out the salient difference in the design approach but however detailed description of the techniques and more examples will be covered separately in a paper on Design and Analysis of Algorithms.
6.2 Recursive algorithms
Before we proceed to discuss the various algorithm design techniques let us restate the definition of recursive algorithms.
Definition
A recursive algorithm is based on replying the algorithm to sub-problems. A recursive algorithm is defined as an algorithm which contains at least one recursive call with “smaller (or simpler)” input values. A recursive call is a call of the same algorithm either directly (algorithm A calls itself) or indirectly (algorithm A calls algorithm B which in turn calls algorithm A). The cascade of recursive calls is similar to iterative processing. In other words a recursive algorithm solves a problem by reducing it to an instance of the same problem with smaller input (recursive part) and having smaller instances where the solution is computed directly (base part) without the algorithm making any calls to itself. Each recursive algorithm must contain a particular case for which it returns the result without calling itself again. Recursive algorithms are easy to implement but their implementation is not always efficient (due to the supplementary space on the program stack needed to deal with the recursive calls). Figure 6.1 shows the role of recursive algorithms in algorithm design.
6.3 Brute Force Technique
Brute force method is the simplest of the design techniques and is based directly on the problem’s statement and definitions of the concepts involved. The approach is to directly design and is the easiest strategy to apply. The results obtained using the algorithm can be improved with a modest amount of time. Brute force is important due to its wide applicability and simplicity. For some important problems such as sorting, searching, string matching etc. the brute-force approach brute force methods provide a reasonable solution for large sample size. Unlike some of the other strategies, brute force is applicable to almost all problems. The basic weakness is the below par efficiency of most brute-force algorithms.
Power(x,n)
p←1
FOR i ← 1,n DO
p ← p*x
ENDFOR
RETURN p
Figure 6.2 Computation of xn
Some of the problems that have been designed using brute force method are given below:
Multiplying two matrices
Searching for a key of a given value in a list
Exhaustive search: Travelling Saleman Problem, knapsack
Simple sorts: selection sort, bubble sort
Computing n!
Computing an (a > 0, n a nonnegative integer)
Let us see two problems that have been solved using the brute force technique.
The first problem we will consider is the computation of xn, where x is a real number and n is a natural number.
The Idea here is that xn can be defined as n multiplications of x that is xn = x*x*…*x.
We can now write the algorithm as given in Figure 6.2. The efficiency of the algorithm is of the order of n (O(n)).
The second problem we will consider is the computation n!, where n a natural number (n>=1).
The Idea here is that n! can be defined as n multiplications of the numbers 1 to n that is n! = 1*2*…*n
We can now write the algorithm as given in Figure 6.3. The efficiency of the algorithm is of the order of n O(n).
Factorial(n)
f ← 1
FOR i ← 1,n DO
f ← f*i
ENDFOR
RETURN f
Figure 6.3 Computation of n!
6.4 Decrease and Conquer Technique
The next technique we will consider is the decrease and conquer design technique. The basic idea is to exploit the relationship between the solution of a given instance of a problem and the solution of a smaller instance of the same problem. By successively reducing the problem’s dimension we eventually arrive at a particular case which can be solved directly. This technique is also referred to as inductive or incremental approach. This technique can be implemented either in a top-down or a bottom-up manner. Reduce the problem to smaller problems (by a factor of at least 2) solved recursively and then combine the solutions
The steps in the design of a problem using this technique are as follows:
1. Reduce problem instance to smaller instances of the same problem
2. Solve smaller instance
3. Extend solution of smaller instance to obtain solution to original instance
The main motivation of using this technique is that such an approach could lead us to an algorithm which is more efficient than a brute force algorithm. Another reason of selecting this technique is that sometimes it is easier to describe the solution of a problem by referring to the solution of a smaller problem than to describe explicitly the solution
There are basically three types of Decrease and Conquer. They are as follows:
• Decrease by a constant (usually by 1):
insertion sort
graph traversal algorithms (DFS and BFS)
topological sorting
algorithms for generating permutations, subsets
• Decrease by a constant factor (usually by half)
binary search and bisection method
exponentiation by squaring
• Variable-size decrease
Euclid’s algorithm
selection by partition
Figure 6.3 shows an example of decrease by a constant and decrease by a constant factor.
As you can see from Figure 6.4 in the decrease by a constant example during each recursive call to power3 (x,m-1) the value of m is decreased by a constant. Repeated calls will finally reduce m to a value of 1 which is the terminating condition and the value of x*x is returned.
On the other hand, in the decrease by a constant factor example during each recursive call to power4 (x,nDiv 2) the value of n is decreased by a constant factor. Repeated calls will finally reduce n to a value of 2 which is the terminating condition and the value of x*x is returned.
Decrease-by-One algorithm for Insertion Sort:
Insertion-Sort(A[0…n-1])
{
Insertion-Sort(A[0…n-2])
Insert A[n-1] into the sorted list A[0…n-2]
return the sorted list A[0…n-1]
}
Figure 6.5 Example of Insertion Sort using of Decrease by one Technique
Problems that can be solved using this design technique include the following:
• Insertion sort
• Topological sorting
• Binary Tree traversals (recursion)
• Computing the length of the longest path in a binary tree (recursion)
• Computing Fibonacci numbers (recursion)
A special case of design using Decrease by a constant that is Decrease by one is the Insertion Sort (Figure 6.5). The recursive call to Insertion Sort tackles an array of size one less than the calling algorithm.
6.5 Divide and Conquer
Divide and conquer is the most-well known algorithm design strategy. As the name indicates we divide the original problem and solve smaller problems recursively and thereby conquer the original problem. The solution to the original problem is formed from the solution to the sub problems. There will be at least 2 recursive calls in the routine. However in general, if iterative solutions are available, recursive calls may be relatively inefficient. Examples of problems solved using this design technique include Tower of Hanoi, merge sort and binary tree sort.
The steps in the design of a problem using this technique are as follows:
1. Divide instance of problem into two or more smaller instances
2.Solve smaller instances recursively
3. Obtain solution to original (larger) instance by combining these solutions
The flow of the divide and conquer (Figure 6.6) is that the original problem of size n is divided into two sub-problems of size n/2 and we find solutions to the two sub-problems which leads to the solution to the original problem. By definition this technique generally leads to a recursive algorithm.
Recursion In Divide And Conquer
Smaller instances that result from the divide step are instances of the original problem (true for sort and min problems). If the new instance is a small instance, it is solved using the method for small instances. If the new instance is a large instance, it is solved using the divide-and-conquer method recursively. Generally, performance is best when the smaller instances that result from the divide step are of approximately the same size.
Let us look at an example of finding the minimum element of a large list (Figure 6.7) In the general problem description let us assume that we want to find the minimum of 20 elements. We first divide into two sub-lists of 10 elements each. Then we find the minimum element in each sub-list in some manner. We then compare the minimums of each sub-list to determine the overall minimum. Let us now look at a recursive algorithm (Figure 6.6). In this definition we find the minimum element of each sub-list in a recursive manner. We continue to solve recursively until the termination condition is reached ( when the number of elements <= 2.
|
Recursive Find Min • Find the minimum of 20 elements.
Figure 6.7 Divide and Conquer Design Technique for Find Min |
The next example we will discuss is the MergeSort algorithm (Figure 6.8). Here again we divide the sequence by half and then recursively sort the two halves until the termination condition is reached, in this case when the sequence size is 1. Figure 6.9 shows an example of MergeSort.
| Mergesort
• DIVIDE the input sequence in half • RECURSIVELY sort the two halves basis of the recursion is sequence with 1 key • COMBINE the two sorted subsequences by merging them |
Figure 6.8 MergeSort Algorithm
6.6 Transform and Conquer
The given problem is modified in such a way that it becomes more amenable to find a solution. After this modification, in the second stage the problem is solved. An example of problem simplification methods is presorting.
6.6.1 Three Variations in Transform and Conquer Technique
Instance Simplification
The first variation is Instance Simplification for example by presorting. Let us consider the example of finding the two closest numbers in an array of numbers. Using the Brute force method of design the solution has a time complexity of O(n2). However using the Transform and Conquer with presorting results in time complexity of O(nlogn). Thus instance simplification can summarized as
• Reducing the Problem to a Simpler One
• Techniques:
• Presorting
• Gaussian Elimination
• Search Trees
Another example where presorting results in a more efficient algorithm is where we are given a random list of numbers and have to determine if there are any duplicates. Using the Brute Force method we need to compare every pair and hence the worst case takes O (n^2) time. However the method of Transform and Conquer proves to be more beneficial. Here we first sort the List and compare A [i] with A [i + 1]. The checking results in time complexity of O (n). This in coordination with a good sorting algorithm such as mergesort can result in a time complexity of O (n log n)
Sometimes the transforming can be in the form of changing the representation (Figure 6.10). A typical example of this is the representation using AVL trees (a self-balancing binary search tree) which guarantees a O(nlogn) search. We will discuss AVL trees in detail later on.
Yet another transformation can be problem reduction. Let us consider the example of least common multiple: lcm(m,n) = (m*n)/ gcd(m,n). This can be viewed as a two stage Solution where we transform the original problem into another and then solve the new problem.
6.7 Greedy Techniques
The greedy algorithm is based on the strategy of “take what you can get now”. It works in phases where in each phase the currently best decision is made. The greedy method is a general algorithm design paradigm, where the algorithm makes a sequence of choices where each choice is the one that seems best so far, and only depends on what’s been done so far resulting in the creation of a smaller problem that needs to be solved. In order for greedy heuristic to work, the optimal solution to the big problem must contain optimal solutions to sub-problems.
This technique constructs a solution to an optimization problem (defined by an objective function and a set of constraints) piece by piece through a sequence of choices that are:
• Feasible, i.e. satisfying the constraints
• locally optimal (with respect to some neighborhood definition)
• greedy (in terms of some measure), and irrevocable
For some problems, it yields a globally optimal solution for every instance.
The greedy method is a general algorithm design paradigm, built on the following elements: different choices, collections, or values to find and a score assigned to choices, which we want to either maximize or minimize. It works best when the globally-optimal solution can always be found by a series of local improvements from a starting configuration.
Examples where the greedy technique is used:
• Dijkstra’s algorithm – (shortest path in weighted graphs)
• Prim’s algorithm, Kruskal’s algorithm (minimal spanning tree in weighted graphs)
• Coin exchange problem
• Huffman Trees
6.8 Two Knapsack Problems
Before we proceed to discuss other design techniques, let us describe the Knapsack problem. We will be discussing some of the design techniques using this problem There are two varieties of this problem – 0-1 Knapsack problem and Fractional Knapsack problem.
6.8.1 0-1 Knapsack Problem:
Definition of the problem:
A mouse robbing a field finds n items.(Figure 6.11). Let W Kg be the at most weight of the items he can carry.
ith item: worth vi Rupees & weighing wi Kg
W, wi, vi are integers.
Which Items should he take?
In this definition of the problem the thief can either take an item or leave it. He cannot take a fraction
Fractional Knapsack Problem:
The thief is allowed to take fractions of items.
The approach to solve Knapsack Problem,
• Consider the most valuable load ( jth item) that weighs at most W Kg.
• If jth item is removed from his load, the remaining load must be the most valuable load weighting at most W-wj that he can take from the n-1 original items excluding j.
One of the design techniques to solve this problem is using dynamic programming.
6.9 Dynamic programming
Dynamic programming is applicable when sub-problems are not independent. In this technique when approached as bottom-up, a table of solutions to sub-problems is filled starting with the problem’s smallest sub-problem. A solution to the original instance of the problem is then obtained from the table constructed. Using Bottom-Up Technique the smallest sub-instances are explicitly solved first and the results of these used to construct solutions to progressively larger sub-instances. A typical example is the solution to Fibonacci numbers computed by iteration.
Dynamic programming can also be carried out in a top-down manner using memory functions.
The steps in dynamic Programming can be summarized as follows:
- Constructing a final solution to a problem by building it up dynamically from solutions to smaller (or simpler) sub-problems
- sub-instances are combined to obtain new sub-instances of increasing size, until finally we arrive at a solution to the original problem.
- We make a choice at each step, depending on the solutions available for sub problems
Dynamic Programming is based on the following principles:
- Principle of optimality
- the optimal solution to any nontrivial instance of a problem is a combination of optimal solutions to some of its sub-instances.
- Memoization (for overlapping sub-problems)
- avoid calculating the same thing twice,
This is usually achieved by keeping a table of known results that fills up as sub-instances are solved.
Now let us try to design a solution for the 0-1 Knapsack problem using Dynamic programming. The first step is to define the sub-problems. Let a us consider an optimal solution. Let us take ith item of weight wi– from the n items. Now there are two possibilities – either i is a solution or it is not. If i is in the solution then the sub-problem is as given
Knapsack(n,W) = ci + Knapsack(n-1, W- wi).
If i is not in the solution then the sub-problem is
Knapsack(n,W) = Knapsack(n-1, W)
6.10 Coloring a map
Let us consider the map coloring problem as an example to explain backtracking. Figure 6.12 shows examples of Maps with four colors. The following is the definition of the problem.
You wish to color a map with not more than four colors red, yellow, green, blue
• Adjacent countries must be in different colors
• You don’t have enough information to choose colors
• Each choice leads to another set of choices
• One or more sequences of choices may (or may not) lead to a solution
One of the techniques to solve this problem is using backtracking.
6.11 Backtracking
Let us suppose that we have to make a series of decisions, among various choices, where we don’t have enough information to know what to choose. each decision leads to a new set of choices and some sequence of choices (possibly more than one) may be a solution to your problem. In such a situation, backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”.
One backtracking method is Generate-and-Test methods which are based on exhaustive search in multiple choice problems This is typically used with depth-first state space search problems. Examples of problems that use such a technique are Puzzles
Now let consider the use of backtracking to design the algorithm for a State Space Search problem. For such problems the following are the components:
• initial state
• goal state(s)
• a set of intermediate states
• a set of operators that transform one state into another. Each operator has associated preconditions and postconditions.
• a cost function that evaluates the cost of the operations (optional)
• a utility function that evaluates how close is a given state to the goal state (optional)
In general backtracking is an useful design technique for solving constraint satisfaction problems that involve assigning values to variables according to a set of constraints. Now let us apply backtracking to the map colouring problem. We first takes each colour c from a set of colours C and checks whether for each colour and a country n, country n is not adjacent to a country that has been colored c. If it is not we colour the country c and we recursively call for Colour country n+1.
6.11 Genetic Algorithms
As already discussed optimisation problems generally comprises of a set of constraints and an optimisation function. A solution that satisfies the constraints is said to be feasible. A feasible solution with the best possible value for the optimisation function is considered optimal. The job is to search for good solutions among possible solutions. However the best possible solution may be missed.
Genetic algorithms are generally used when the search space of solutions is large, complex or poorly understood. In the case of genetic algorithms a chromosome is represented as a string which is the code of the solution. The fitness of a string indicates gives a measure of goodness of the solution that it codes. Fitness is calculated by a fitness function. Normally a genetic algorithm is associated with the following operations:
- Selection: choosing two parent chromosomes – Select from a population according to their fitness
- Crossover is the procedure by which two chromosomes mate to create a new offspring chromosome -With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
- Mutation: with a mutation probability flip a bit in the offspring at each locus (position in chromosome).
Basic Genetic Algorithm has the following steps
- Start: Generate random population of n chromosomes (suitable solutions for the problem)
- Fitness: Evaluate the fitness f(x) of each chromosome x in the population
- New population: Create a new population by repeating following steps until the new population is complete
- Test: If the end condition is satisfied, stop, and return the best solution in current population
6.12 Conclusion
The basic question to be answered is how to choose the design approach. The first requirement is a good understanding of the problem and its characteristics. After this step we must know the various problems and how they are solved using different approaches. Then knowing the problem characteristics, we can chose an approach that has been previously used to solve problems with similar characteristics.
Summary
In this module we discussed
- the different design techniques and
- explained the techniques using illustrative examples .
| you can view video on Design of Algorithms | |
