ALGORITHM DESIGN TECHNIQUE
There are primarily two main categories into which an algorithm can be
named in this type of classification. They are:
Greedy Method: In the greedy method, at each step, a decision is made
to choose the local optimum, without thinking about the future
consequences.
Example: Fractional Knapsack, Activity Selection.
Divide and Conquer: The Divide and Conquer strategy involves dividing
the problem into sub-problem, recursively solving them, and then
recombining them for the final answer.
Example: Binary search, finding maximum and minimum and
1.) Divide and Conquer
Introduction
Divide and Conquer approach basically works on breaking the problem
into sub problems that are similar to the original problem but smaller in
size & simpler to solve. Once divided sub problems are solved
recursively and then combine solutions of sub problems to create a
solution to original problem.
At each level of the recursion the divide and conquer approach follows
three steps:
Divide: In this step whole problem is divided into several sub problems.
Conquer: The sub problems are conquered by solving them recursively,
only if they are small enough to be solved, otherwise step1 is executed.
Combine: In this final step, the solution obtained by the sub problems
are combined to create solution to the original problem.
Generally, we can follow the divide and conquer approach in a three-
step process.
Examples: The specific computer algorithms are based on the Divide &
Conquer approach:
1. Maximum and Minimum Problem
2. Binary Search
3. Sorting (merge sort, quick sort)
4. Tower of Hanoi.
Fundamental of Divide & Conquer Strategy:
There are two fundamentals of Divide & Conquer Strategy:
1. Relational Formula
2. Stopping Condition
1. Relational Formula: It is the formula that we generate from the given
technique.
After generation of Formula, we apply D&C Strategy, i.e., we break the
problem recursively & solve the broken sub problems.
2. Stopping Condition: When we break the problem using Divide &
Conquer Strategy, then we need to know that for how much time, we
need to apply divide & Conquer. So, that the condition where it need to
stop out recursion steps of D&C is called as Stopping Condition.
Applications of Divide and Conquer Approach:
Following algorithms are based on the concept of the Divide and
Conquer Technique:
1. Binary Search: The binary search algorithm is a searching
algorithm, which is also called a half-interval search or logarithmic
search. It works by comparing the target value with the middle
element existing in a sorted array. After making the comparison, if
the value differs, then the half that cannot contain the target will
eventually eliminate, followed by continuing the search on the
other half. We will again consider the middle element and compare
it with the target value. The process keeps on repeating until the
target value is met. If we found the other half to be empty after
ending the search, then it can be concluded that the target is not
present in the array.
2. Quicksort: It is the most efficient sorting algorithm, which is also
known as partition-exchange sort. It starts by selecting a pivot value
from an array followed by dividing the rest of the array elements into
two sub-arrays. The partition is made by comparing each of the elements
with the pivot value. It compares whether the element holds a greater
value or lesser value than the pivot and then sort the arrays recursively.
3. Merge Sort: It is a sorting algorithm that sorts an array by making
comparisons.
It starts by dividing an array into sub-array and then recursively sorts
each of them. After the sorting is done, it merges them back.
Advantages of Divide and Conquer
Divide and Conquer tend to successfully solve one of the biggest
problems, such as the Tower of Hanoi, a mathematical puzzle. It is
challenging to solve complicated problems for which you have no basic
idea, but with the help of the divide and conquer approach, it has
lessened the effort as it works on dividing the main problem into two
halves and then solve them recursively. This algorithm is much faster
than other algorithms.
It efficiently uses cache memory without occupying much space
because it solves simple sub problems within the cache memory instead
of accessing the slower main memory.
Disadvantages of Divide and Conquer
Since most of its algorithms are designed by incorporating recursion, so
it necessitates high memory management.
An explicit stack may overuse the space.
It may even crash the system if the recursion is performed rigorously
greater than the stack present in the CPU.
2 Backtracking
Introduction
The Backtracking is an algorithmic-method to solve a problem with an
additional way. It uses a recursive approach to explain the problems. We
can say that the backtracking is needed to find all possible combination
to solve an optimization problem.
Backtracking is a systematic way of trying out different sequences of
decisions until we find one that "works."
In the following Figure:
Each non-leaf node in a tree is a parent of one or more other nodes (its
children)
Each node in the tree, other than the root, has exactly one parent
Generally, however, we draw our trees downward, with the root at the
top.
A tree is composed of nodes.
Backtracking can understand of as searching a tree for a particular
"goal" leaf node.
Backtracking is undoubtedly quite simple - we "explore" each node, as
follows:
To "explore" node N:
1. If N is a goal node, return "success"
2. If N is a leaf node, return "failure"
3. For each child C of N,
Explore C
If C was successful, return "success"
4. Return "failure"
Backtracking algorithm determines the solution by systematically
searching the solution space for the given problem. Backtracking is a
depth-first search with any bounding function. All solution using
backtracking is needed to satisfy a complex set of constraints.
The constraints may be explicit or implicit.
Explicit Constraint is ruled, which restrict each vector element to be
chosen from the given set.
Implicit Constraint is ruled, which determine which each of the tuples in
the solution space, actually satisfy the criterion function
3 Dynamic programming
Dynamic Programming Technique is similar to divide-and-conquer
technique. Both techniques solve a problem by breaking it down into
several sub-problems that can be solved recursively.
The main difference between is that, Divide & Conquer approach
partitions the problems into independent sub-problems, solve the sub-
problems recursively, and then combine their solutions to solve the
original problems. Whereas
dynamic programming is applicable when the sub-problems are not
independent, that is,
when sub-problems share sub subproblems. Also, A dynamic
programming algorithms solves every sub problem just once and then
saves its answer in a table, thereby avoiding the work of recomputing the
answer every time the sub subproblems is encountered.
Therefore "Dynamic programming is a applicable when sub problem are
not independent, that is when sub problem share sub problems."
As Greedy approach, Dynamic programming is typically applied to
optimization problems and for them there can be many possible
solutions and the requirement is tofind the optimal solution among those.
But Dynamic programming approach is little different greedy approach.
In greedy solutions are computed by making choices in serial forward
way and in this no backtracking & revision of choices is done where as
Dynamic programming computes its solution bottom up by producing
them from smaller sub problems, and by trying many possibilities and
choices before it arrives at the optimal set of choices.
The Development of a dynamic-programming algorithm can be broken
into a sequence of four steps:
Divide, Sub problems: The main problems are divided into several
smaller sub problems. In this the solution of the main problem is
expressed in terms of the solution for the smaller sub problems.
Basically, it is all about characterizing the structure of an
optimal solution and recursively define the value of an optimal solution.
Table, Storage: The solution for each sub problem is stored in a table, so
that it can be used many times whenever required.
Combine, bottom-up Computation: The solution to main problem is
obtained by combining the solutions of smaller sub problems. i.e.,
compute the value of an optimal solution in a bottom-up fashion.
Construct an optimal solution from computed information. (This step is
optional and is required in case if some additional information is
required after finding out optimal solution.)
Now for any problem to be solved through dynamic programming
approach it must follow the following conditions:
Principle of Optimality: It states that for solving the master problem
optimally, its sub problems should be solved optimally. It should be
noted that not all the times each sub problem(s) is solved optimally, so
in that case we should go for optimal majority.
Polynomial Breakup: For solving the main problem, the problem is
divided into several sub problems and for efficient performance of
dynamic programming the total number of sub problems to be solved
should be at-most a polynomial number.
Various algorithms which make use of Dynamic programming technique
are as follows:
1. Knapsack problem.
2. Chain matrix multiplication.
3. All pair shortest path.
4. Travelling sales man problem.
5. Tower of hanoi.
6. Checker Board.
7. Fibonacci Sequence.
8. Assembly line scheduling.
9. Optimal binary search trees.