Divide and Conquer Introduction

Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is

to take a dispute on a huge input, break the input into minor pieces, decide the
problem on each of the small pieces, and then merge the piecewise solutions into a
global solution. This mechanism of solving the problem is called the Divide &
Conquer Strategy.

Divide and Conquer algorithm consists of a dispute using the following three steps.

1. Divide the original problem into a set of subproblems.

2. Conquer: Solve every subproblem individually, recursively.
3. Combine: Put together the solutions of the subproblems to get the solution
to the whole 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 fundamental 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 subproblems.

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 the condition where the need to stop our 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

o 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.
o It efficiently uses cache memory without occupying much space because it
solves simple subproblems within the cache memory instead of accessing the
slower main memory.
o It is more proficient than that of its counterpart Brute Force technique.
o Since these algorithms inhibit parallelism, it does not involve any modification
and is handled by systems incorporating parallel processing.

AD
AD

Disadvantages of Divide and Conquer

o Since most of its algorithms are designed by incorporating recursion, so it
necessitates high memory management.
o An explicit stack may overuse the space.
o It may even crash the system if the recursion is performed rigorously greater
than the stack present in the CPU.

Greedy Algorithm
The greedy method is one of the strategies like Divide and conquer used to solve the
problems. This method is used for solving optimization problems. An optimization
problem is a problem that demands either maximum or minimum results. Let's
understand through some terms.

The Greedy method is the simplest and straightforward approach. It is not an

algorithm, but it is a technique. The main function of this approach is that the
decision is taken on the basis of the currently available information. Whatever the
current information is present, the decision is made without worrying about the
effect of the current decision in future.

This technique is basically used to determine the feasible solution that may or may
not be optimal. The feasible solution is a subset that satisfies the given criteria. The
optimal solution is the solution which is the best and the most favorable solution in
the subset. In the case of feasible, if more than one solution satisfies the given
criteria then those solutions will be considered as the feasible, whereas the optimal
solution is the best solution among all the solutions.

Characteristics of Greedy method

The following are the characteristics of a greedy method:

o To construct the solution in an optimal way, this algorithm creates two sets where one
set contains all the chosen items, and another set contains the rejected items.
o A Greedy algorithm makes good local choices in the hope that the solution should be
either feasible or optimal.

Components of Greedy Algorithm

The components that can be used in the greedy algorithm are:

o Candidate set: A solution that is created from the set is known as a candidate set.
o Selection function: This function is used to choose the candidate or subset which
can be added in the solution.
o Feasibility function: A function that is used to determine whether the candidate or
subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution or the
partial solution.
o Solution function: This function is used to intimate whether the complete function
has been reached or not.
AD
AD

Applications of Greedy Algorithm

o It is used in finding the shortest path.
o It is used to find the minimum spanning tree using the prim's algorithm or the
Kruskal's algorithm.
o It is used in a job sequencing with a deadline.
o This algorithm is also used to solve the fractional knapsack problem.

Pseudo code of Greedy Algorithm

1. Algorithm Greedy (a, n)
2. {
3. Solution : = 0;
4. for i = 0 to n do
5. {
6. x: = select(a);
7. if feasible(solution, x)
8. {
9. Solution: = union(solution , x)
10. }
11. return solution;
12. } }

The above is the greedy algorithm. Initially, the solution is assigned with zero value.
We pass the array and number of elements in the greedy algorithm. Inside the for
loop, we select the element one by one and checks whether the solution is feasible
or not. If the solution is feasible, then we perform the union.

Let's understand through an example.

Suppose there is a problem 'P'. I want to travel from A to B shown as below:

P:A→B

The problem is that we have to travel this journey from A to B. There are various
solutions to go from A to B. We can go from A to B by walk, car, bike, train,
aeroplane, etc. There is a restriction in the journey that we have to travel this journey
within 12 hrs. If I go by train or aeroplane then only, I can cover this distance within
12 hrs. There are many solutions to this problem but there are only two solutions
that satisfy the constraint(restriction).
If we say that we have to cover the journey at the minimum cost. This means that we
have to travel this distance as minimum as possible, so this problem is known as a
minimization problem. Till now, we have two feasible solutions, i.e., one by train and
another one by air. Since travelling by train will lead to the minimum cost so it is an
optimal solution. An optimal solution is also the feasible solution, but providing the
best result so that solution is the optimal solution with the minimum cost. There
would be only one optimal solution.

The problem that requires either minimum or maximum result then that problem is
known as an optimization problem. Greedy method is one of the strategies used for
solving the optimization problems.

Disadvantages of using Greedy algorithm

Greedy algorithm makes decisions based on the information available at each phase
without considering the broader problem. So, there might be a possibility that the
greedy solution does not give the best solution for every problem.

It follows the local optimum choice at each stage with a intend of finding the global
optimum. Let's understand through an example.

Consider the graph which is given below:

We have to travel from the source to the destination at the minimum cost. Since we
have three feasible solutions having cost paths as 10, 20, and 5. 5 is the minimum
cost path so it is the optimal solution. This is the local optimum, and in this way, we
find the local optimum at each stage in order to calculate the global optimal
solution.

Dynamic Programming
Dynamic programming is a technique that breaks the problems into sub-problems,
and saves the result for future purposes so that we do not need to compute the
result again. The subproblems are optimized to optimize the overall solution is
known as optimal substructure property. The main use of dynamic programming is
to solve optimization problems. Here, optimization problems mean that when we are
trying to find out the minimum or the maximum solution of a problem. The dynamic
programming guarantees to find the optimal solution of a problem if the solution
exists.

The definition of dynamic programming says that it is a technique for solving a

complex problem by first breaking into a collection of simpler subproblems, solving
each subproblem just once, and then storing their solutions to avoid repetitive
computations.

Let's understand this approach through an example.

Consider an example of the Fibonacci series. The following series is the

Fibonacci series:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…

The numbers in the above series are not randomly calculated. Mathematically, we
could write each of the terms using the below formula:

F(n) = F(n-1) + F(n-2),

With the base values F(0) = 0, and F(1) = 1. To calculate the other numbers, we follow
the above relationship. For example, F(2) is the sum f(0) and f(1), which is equal to 1.

How can we calculate F(20)?

The F(20) term will be calculated using the nth formula of the Fibonacci series. The
below figure shows that how F(20) is calculated.
As we can observe in the above figure that F(20) is calculated as the sum of F(19) and
F(18). In the dynamic programming approach, we try to divide the problem into the
similar subproblems. We are following this approach in the above case where F(20)
into the similar subproblems, i.e., F(19) and F(18). If we recap the definition of
dynamic programming that it says the similar subproblem should not be computed
more than once. Still, in the above case, the subproblem is calculated twice. In the
above example, F(18) is calculated two times; similarly, F(17) is also calculated twice.
However, this technique is quite useful as it solves the similar subproblems, but we
need to be cautious while storing the results because we are not particular about
storing the result that we have computed once, then it can lead to a wastage of
resources.

In the above example, if we calculate the F(18) in the right subtree, then it leads to
the tremendous usage of resources and decreases the overall performance.

The solution to the above problem is to save the computed results in an array. First,
we calculate F(16) and F(17) and save their values in an array. The F(18) is calculated
by summing the values of F(17) and F(16), which are already saved in an array. The
computed value of F(18) is saved in an array. The value of F(19) is calculated using
the sum of F(18), and F(17), and their values are already saved in an array. The
computed value of F(19) is stored in an array. The value of F(20) can be calculated by
adding the values of F(19) and F(18), and the values of both F(19) and F(18) are
stored in an array. The final computed value of F(20) is stored in an array.
How does the dynamic programming approach
work?
The following are the steps that the dynamic programming follows:

o It breaks down the complex problem into simpler subproblems.

o It finds the optimal solution to these sub-problems.
o It stores the results of subproblems (memorization). The process of storing the results
of subproblems is known as memorization.
o It reuses them so that same sub-problem is calculated more than once.
o Finally, calculate the result of the complex problem.

The above five steps are the basic steps for dynamic programming. The dynamic
programming is applicable that are having properties such as:

Those problems that are having overlapping subproblems and optimal substructures.
Here, optimal substructure means that the solution of optimization problems can be
obtained by simply combining the optimal solution of all the subproblems.

In the case of dynamic programming, the space complexity would be increased as we

are storing the intermediate results, but the time complexity would be decreased.

Approaches of dynamic programming

There are two approaches to dynamic programming:

AD

AD

o Top-down approach
o Bottom-up approach

AD
AD

Top-down approach
The top-down approach follows the memorization technique, while bottom-up
approach follows the tabulation method. Here memorization is equal to the sum of
recursion and caching. Recursion means calling the function itself, while caching
means storing the intermediate results.

Advantages
 o It is very easy to understand and implement.
o It solves the subproblems only when it is required.
o It is easy to debug.

Disadvantages

It uses the recursion technique that occupies more memory in the call stack.
Sometimes when the recursion is too deep, the stack overflow condition will occur.

It occupies more memory that degrades the overall performance.

AD

AD

Let's understand dynamic programming through an example.

1. int fib(int n)
2. {
3. if(n<0)
4. error;
5. if(n==0)
6. return 0;
7. if(n==1)
8. return 1;
9. sum = fib(n-1) + fib(n-2);
10. }

In the above code, we have used the recursive approach to find out the Fibonacci
series. When the value of 'n' increases, the function calls will also increase, and
computations will also increase. In this case, the time complexity increases
exponentially, and it becomes 2n.

One solution to this problem is to use the dynamic programming approach. Rather
than generating the recursive tree again and again, we can reuse the previously
calculated value. If we use the dynamic programming approach, then the time
complexity would be O(n).

When we apply the dynamic programming approach in the implementation of the

Fibonacci series, then the code would look like:

1. static int count = 0;

2. int fib(int n)
 3. {
4. if(memo[n]!= NULL)
5. return memo[n];
6. count++;
7. if(n<0)
8. error;
9. if(n==0)
10. return 0;
11. if(n==1)
12. return 1;
13. sum = fib(n-1) + fib(n-2);
14. memo[n] = sum;
15. }

In the above code, we have used the memorization technique in which we store the
results in an array to reuse the values. This is also known as a top-down approach in
which we move from the top and break the problem into sub-problems.

Bottom-Up approach
The bottom-up approach is also one of the techniques which can be used to
implement the dynamic programming. It uses the tabulation technique to implement
the dynamic programming approach. It solves the same kind of problems but it
removes the recursion. If we remove the recursion, there is no stack overflow issue
and no overhead of the recursive functions. In this tabulation technique, we solve the
problems and store the results in a matrix.

There are two ways of applying dynamic programming:

o Top-Down
o Bottom-Up

The bottom-up is the approach used to avoid the recursion, thus saving the memory
space. The bottom-up is an algorithm that starts from the beginning, whereas the
recursive algorithm starts from the end and works backward. In the bottom-up
approach, we start from the base case to find the answer for the end. As we know,
the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts
from the base cases, so we will start from 0 and 1.

Key points
 o We solve all the smaller sub-problems that will be needed to solve the larger sub-
problems then move to the larger problems using smaller sub-problems.
o We use for loop to iterate over the sub-problems.
o The bottom-up approach is also known as the tabulation or table filling method.

Let's understand through an example.

Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions,
respectively shown as below:

Since the bottom-up approach starts from the lower values, so the values at a[0] and
a[1] are added to find the value of a[2] shown as below:

The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown
as below:

The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown
as below:

The value of a[5] will be calculated by adding the values of a[4] and a[3], and it
becomes 5 shown as below:
In the above code, base cases are 0 and 1 and then we have used for loop to find
other values of Fibonacci series.

Let's understand through the diagrammatic representation.

Initially, the first two values, i.e., 0 and 1 can be represented as:

When i=2 then the values 0 and 1 are added shown as below:

When i=3 then the values 1and 1 are added shown as below:
When i=4 then the values 2 and 1 are added shown as below:

When i=5, then the values 3 and 2 are added shown as below:
In the above case, we are starting from the bottom and reaching to the top.

Branch and bound vs backtracking

Before understanding the branch and bound and backtracking differences, we should
know about the branch and bound and backtracking separately.

What is Backtracking?

Backtracking is nothing but the modified process of the Brute force approach. It is a
technique where multiple solutions to a problem are available, and it searches for the
solution to the problem among all the available options. Let's consider the example
of brute force search as backtracking follows the brute force search approach.

Consider the box, and we have three objects of three different colors. One object is
of red color, the second object is of green color, and the third object is of blue color.
Now, we have to keep these objects inside the box, and we have multiple options. As
per the Brute force approach, we have to consider all the options and identify the
best option among all the possible options.

Let's consider all the possible solutions to this problem.

Suppose we first fill red object, after then green object and then blue object. This is
the first solution to this problem. The possible solution is red, green, and blue.
The second solution is to keep the red object, then the blue object, and then the
green object. The possible solution red, blue, and green.

The third solution can be to keep the green object, then the red object and then the
blue object. The possible solution is green, red and blue.

The fourth solution is to keep the green object, then the blue object and then the red
object. The possible solution is green, blue and red.

The fifth solution is to keep the blue object, then green object and then red object.
The possible solution is blue, green and red.

The sixth solution is to keep the blue object, then the red object and then the green
object. The possible solution is blue, red and green.
The above are the possible solutions, and we have to identify the best possible
solution out of all the possible solutions. This approach is known as a brute force
approach. Backtracking is similar to the brute force approach, but it is a modified
process of the brute force approach.

Let's see how backtracking is different from the brute force approach.

The above is the figure that shows the possible solutions to the above problem. Now
we will see that how these solutions are represented in backtracking.

In backtracking, solutions are represented in the form of a tree and that tree is
known as a state space tree. Since backtracking follows the DFS, the tree will be
formed using DFS, which is known as a State Space tree.

Let's create the tree.

Consider the first solution, i.e., red, green, blue, and it can be represented in the
form of a tree as shown as below.

AD

AD
Consider the second solution, i.e., red, blue, green. Since there is no more object
after blue so we will backtrack and move to the green. Instead of taking green, we
first take blue and then green, shown as below:

The next solution is green, red and blue. Since we cannot explore the green object,
so we move back and reach the blue object. We cannot explore the blue object, so
we again move back and reach to the red object. Instead of using the red object, we
will use the green object. After the green object, we use the red object and then we
use the blue object. We cannot explore the blue object further. Now the sequence
green, red and blue is formed as shown as below:
The next solution is green, blue and red. Since we cannot explore the blue object,
we move back and reach the red object. Instead of using a red color object, we will
use the blue color object and then we use the red color object. Now the sequence
green, blue and red is formed.

The next solution is blue, green and red. Since we cannot explore the red object, so
we backtrack and reach the blue object. We cannot explore the blue object so we
backtrack and reach the green object. Instead of using the green object, we will use
the blue color object then we use the green object and then we use the red color
object. The sequence, i.e., blue, green and red, is formed as shown as below:

The next solution is blue, red and green. Since we cannot explore red object so we
backtrack and reach to the green object. Instead of using the green object, we use
the red object and then we use the green object.

AD

AD

The above is the state space tree that shows all the possible solutions related to the
problem. Therefore, we can say that the state space tree can be used to represent all
the solutions in backtracking. Using backtracking, we can solve the problem that has
some constraints and we can find the solution based on these constraints. Suppose
in the above example; the constraint is blue color object must not be in the middle
(bounding function).

The first solution is red, green and blue. Since blue color object is not in the middle
so we do need to perform any modification.

The second solution is red, blue, and green. Since blue color is in the middle so we
will remove the green color as shown as below:

The next solution is green, red, and blue. Since blue color object is not in the
middle so we do need to perform any modification.

The next solution is green, blue and red. Since blue color is in the middle so we will
remove the red color as shown as below:
The above is the state space tree that does not have blue object in the middle of the
solution.

Branch and Bound

It is similar to backtracking. The concept branch and bound and backtracking follow
the Brute force method and generate the state space tree. But both of them follows
different approaches. The way to generate the tree is different.

Backtracking follows the DFS, whereas the branch n bound follows the BFS to
generate the tree. Now we will understand the branch n bound through an example.
As it follows the BFS, so first all the nodes of the same level are added then we move
to the next level.

Consider the same example that we discussed in the backtracking.

First, we take the root node.

Now we have three possibilities that either we select red, green, or blue objects as
shown below. In this case, we have completed the first level.
Now we move to the next level.

In the case of red object, we have two possibilities that either we select green or blue
object shown as below:

In the case of green object, we have two possibilities that either we select red or blue
object shown as below:

In the case of blue object, we have two possibilities that either we select red or green
object shown as below:
We move to the third level.

In the case of a green object, only one object, i.e., blue, can be added.

In the case of a blue object, only one object, i.e., green, can be added.
In the case of a red object, only one object, i.e., blue, can be added.

In the case of a blue object, only one object, i.e., red, can be added.
In the case of a green object, only one object, i.e., red, can be added.

In the case of a red object, only one object, i.e., green, can be added.
 Examples:

The problems that can be solved by using backtracking are:

o 8 Queens problem
o Knapsack problem using backtracking

The problem that can be solved by using branch and bound is:

o Travelling Salesman Problem

AD
AD

Differences between Branch n bound and

Backtracking

Backtracking Branch and bound

Backtracking is a problem-solving technique so it solves Branch n bound is a problem-solving

the decision problem. technique so it solves the optimization
problem.

When we find the solution using backtracking then some When we find the solution using Branch n
bad choices can be made. bound then it provides a better solution so
 there are no chances of making a bad choice.

Backtracking uses a Depth first search. It is not necessary that branch n bound uses
Depth first search. It can even use a Breadth-
first search and best-first search.

The state space tree is searched until the solution of the The state space tree needs to be searched
problem is obtained. completely as the optimum solution can be
present anywhere in the state space tree.

In backtracking, all the possible solutions are tried. If the In branch and bound, based on search;
solution does not satisfy the constraint, then we bounding values are calculated. According to
backtrack and look for another solution. the bounding values, we either stop there or
extend.

Applications of backtracking are n-Queens problem, Sum Applications of branch and bound are
of subset. knapsack problem, travelling salesman
problem, etc.

Backtracking is more efficient than the Branch and Branch n bound is less efficient.
bound.

It contains the feasibility function. It contains the bounding function.

Backtracking solves the given problem by first finding the Branch and bound solves the given problem
solution of the subproblem and then recursively solves by dividing the problem into two atleast
the other problems based on the solution of the first subproblems.
subproblem.

Algorithm Design Techniques

The following is a list of several popular design approaches:

1. Divide and Conquer Approach: It is a top-down approach. The algorithms which

follow the divide & conquer techniques involve three steps:

o Divide the original problem into a set of subproblems.

o Solve every subproblem individually, recursively.
 o Combine the solution of the subproblems (top level) into a solution of the
whole original problem.

2. Greedy Technique: Greedy method is used to solve the optimization problem. An

optimization problem is one in which we are given a set of input values, which are
required either to be maximized or minimized (known as objective), i.e. some
constraints or conditions.

o Greedy Algorithm always makes the choice (greedy criteria) looks best at the
moment, to optimize a given objective.
o The greedy algorithm doesn't always guarantee the optimal solution however
it generally produces a solution that is very close in value to the optimal.

AD

3. Dynamic Programming: Dynamic Programming is a bottom-up approach we

solve all possible small problems and then combine them to obtain solutions for
bigger problems.

This is particularly helpful when the number of copying subproblems is exponentially

large. Dynamic Programming is frequently related to Optimization Problems.

4. Branch and Bound: In Branch & Bound algorithm a given subproblem, which
cannot be bounded, has to be divided into at least two new restricted subproblems.
Branch and Bound algorithm are methods for global optimization in non-convex
problems. Branch and Bound algorithms can be slow, however in the worst case they
require effort that grows exponentially with problem size, but in some cases we are
lucky, and the method coverage with much less effort.

5. Randomized Algorithms: A randomized algorithm is defined as an algorithm that

is allowed to access a source of independent, unbiased random bits, and it is then
allowed to use these random bits to influence its computation.

6. Backtracking Algorithm: Backtracking Algorithm tries each possibility until they

find the right one. It is a depth-first search of the set of possible solution. During the
search, if an alternative doesn't work, then backtrack to the choice point, the place
which presented different alternatives, and tries the next alternative.

7. Randomized Algorithm: A randomized algorithm uses a random number at least

once during the computation make a decision.

Example 1: In Quick Sort, using a random number to choose a pivot.

Example 2: Trying to factor a large number by choosing a random number as
possible divisors.

Loop invariants
This is a justification technique. We use loop invariant that helps us to understand
why an algorithm is correct. To prove statement S about a loop is correct, define S
concerning series of smaller statement S0 S1....Sk where,

o The initial claim so is true before the loop begins.

o If Si-1 is true before iteration i begin, then one can show that S i will be true
after iteration i is over.
o The final statement Sk implies the statement S that we wish to justify as being
true.

Bin Packing Problem (Minimize number of

used Bins)



Given n items of different weights and bins each of capacity c, assign each item to a
bin such that number of total used bins is minimized. It may be assumed that all items
have weights smaller than bin capacity.
Example:
Input: weight[] = {4, 8, 1, 4, 2, 1}
Bin Capacity c = 10
Output: 2
We need minimum 2 bins to accommodate all items
First bin contains {4, 4, 2} and second bin {8, 1, 1}

Input: weight[] = {9, 8, 2, 2, 5, 4}

Bin Capacity c = 10
Output: 4
We need minimum 4 bins to accommodate all items.

Input: weight[] = {2, 5, 4, 7, 1, 3, 8};

Bin Capacity c = 10
Output: 3
Lower Bound
We can always find a lower bound on minimum number of bins required. The lower
bound can be given as :
Min no. of bins >= Ceil ((Total Weight) / (Bin Capacity))
In the above examples, lower bound for first example is “ceil(4 + 8 + 1 + 4 + 2 +
1)/10” = 2 and lower bound in second example is “ceil(9 + 8 + 2 + 2 + 5 + 4)/10” = 3.
This problem is a NP Hard problem and finding an exact minimum number of bins
takes exponential time. Following are approximate algorithms for this problem.
Applications
1. Loading of containers like trucks.
2. Placing data on multiple disks.
3. Job scheduling.
4. Packing advertisements in fixed length radio/TV station breaks.
5. Storing a large collection of music onto tapes/CD’s, etc.
Online Algorithms
These algorithms are for Bin Packing problems where items arrive one at a time (in
unknown order), each must be put in a bin, before considering the next item.
1. Next Fit:
When processing next item, check if it fits in the same bin as the last item. Use a new
bin only if it does not.
Next Fit is a simple algorithm. It requires only O(n) time and O(1) extra space to
process n items.
Next Fit is 2 approximate, i.e., the number of bins used by this algorithm is bounded
by twice of optimal. Consider any two adjacent bins. The sum of items in these two
bins must be > c; otherwise, NextFit would have put all the items of second bin into
the first. The same holds for all other bins. Thus, at most half the space is wasted, and
so Next Fit uses at most 2M bins if M is optimal.
2. First Fit:
When processing the next item, scan the previous bins in order and place the item in
the first bin that fits. Start a new bin only if it does not fit in any of the existing bins.
The above implementation of First Fit requires O(n2) time, but First Fit can be
implemented in O(n Log n) time using Self-Balancing Binary Search Trees.
If M is the optimal number of bins, then First Fit never uses more than 1.7M bins. So
First-Fit is better than Next Fit in terms of upper bound on number of bins.
Auxiliary Space: O(n)
3. Best Fit:
The idea is to places the next item in the *tightest* spot. That is, put it in the bin so
that the smallest empty space is left.
Best Fit can also be implemented in O(n Log n) time using Self-Balancing Binary
Search Trees.
If M is the optimal number of bins, then Best Fit never uses more than 1.7M bins. So
Best Fit is same as First Fit and better than Next Fit in terms of upper bound on
number of bins.
Auxiliary Space: O(n)
4. Worst Fit:
The idea is to places the next item in the least tight spot to even out the bins. That is,
put it in the bin so that most empty space is left.
Worst Fit can also be implemented in O(n Log n) time using Self-Balancing Binary
Search Trees.
If M is the optimal number of bins, then Best Fit never uses more than 2M-2 bins. So
Worst Fit is same as Next Fit in terms of upper bound on number of bins.
Auxiliary Space: O(n)

Offline Algorithms
In the offline version, we have all items upfront. Unfortunately offline version is also
NP Complete, but we have a better approximate algorithm for it. First Fit Decreasing
uses at most (4M + 1)/3 bins if the optimal is M.
4. First Fit Decreasing:
A trouble with online algorithms is that packing large items is difficult, especially if
they occur late in the sequence. We can circumvent this by *sorting* the input
sequence, and placing the large items first. With sorting, we get First Fit Decreasing
and Best Fit Decreasing, as offline analogues of online First Fit and Best Fit.
First Fit decreasing produces the best result for the sample input because items are
sorted first.
First Fit Decreasing can also be implemented in O(n Log n) time using Self-Balancing
Binary Search Trees.
Auxiliary Space: O(1)

0-1 Knapsack Problem

We discussed the fractional knapsack problem using the
greedy approach, earlier in this tutorial. It is shown that
Greedy approach gives an optimal solution for Fractional
Knapsack. However, this chapter will cover 0-1 Knapsack
problem using dynamic programming approach and its
analysis.
Unlike in fractional knapsack, the items are always stored fully
without using the fractional part of them. Its either the item is
added to the knapsack or not. That is why, this method is known
as the 0-1 Knapsack problem.
Hence, in case of 0-1 Knapsack, the value of xi can be
either 0 or 1, where other constraints remain the same.

0-1 Knapsack cannot be solved by Greedy approach. Greedy

approach does not ensure an optimal solution in this method. In
many instances, Greedy approach may give an optimal solution.

0-1 Knapsack Algorithm

Problem Statement − A thief is robbing a store and can carry a
maximal weight of W into his knapsack. There are n items and
weight of ith item is wi and the profit of selecting this item is pi.
What items should the thief take?
Let i be the highest-numbered item in an optimal
solution S for W dollars. Then S’ = S − {i} is an optimal solution
for W – wi dollars and the value to the solution S is Vi plus the
value of the sub-problem.
We can express this fact in the following formula: define c[i, w] to
be the solution for items 1,2, … , i and the maximum weight w.

The algorithm takes the following inputs

 The maximum weight W

 The number of items n
 The two sequences v = <v1, v2, …, vn> and w = <w1, w2, …, wn>
The set of items to take can be deduced from the table, starting
at c[n, w] and tracing backwards where the optimal values came
from.
If c[i, w] = c[i-1, w], then item i is not part of the solution, and we
continue tracing with c[i-1, w]. Otherwise, item i is part of the
solution, and we continue tracing with c [i-1, w-W].
Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
c[0, w] = 0
for i = 1 to n do
c[i, 0] = 0
for w = 1 to W do
if wi ≤ w then
if vi + c[i-1, w-wi] then
c[i, w] = vi + c[i-1, w-wi]
else c[i, w] = c[i-1, w]
else
c[i, w] = c[i-1, w]

The following examples will establish our statement.

Example

Let us consider that the capacity of the knapsack is W = 8 and

the items are as shown in the following table.

Item A B C
 Profit 2 4 7

Weight 1 3 5

Solution

Using the greedy approach of 0-1 knapsack, the weight that’s

stored in the knapsack would be A+B = 4 with the maximum
profit 2 + 4 = 6. But, that solution would not be the optimal
solution.

Therefore, dynamic programming must be adopted to solve 0-1

knapsack problems.

Step 1

Construct an adjacency table with maximum weight of knapsack

as rows and items with respective weights and profits as
columns.

Values to be stored in the table are cumulative profits of the

items whose weights do not exceed the maximum weight of the
knapsack (designated values of each row)

So we add zeroes to the 0th row and 0th column because if the
weight of item is 0, then it weighs nothing; if the maximum
weight of knapsack is 0, then no item can be added into the
knapsack.
The remaining values are filled with the maximum profit
achievable with respect to the items and weight per column that
can be stored in the knapsack.

The formula to store the profit values is −

[Math Processing Error]𝑐[𝑖,𝑤]=𝑚𝑎𝑥{𝑐[𝑖−1,𝑤−𝑤[𝑖]]+𝑃[𝑖]}

By computing all the values using the formula, the table obtained
would be −
To find the items to be added in the knapsack, recognize the
maximum profit from the table and identify the items that make
up the profit, in this example, its {1, 7}.

The optimal solution is {1, 7} with the maximum profit is 12.

Analysis
This algorithm takes Ɵ(n.w) times as table c has (n+1).(w+1)
entries, where each entry requires Ɵ(1) time to compute.

Travelling Salesman Problem using Dynamic

Programming




Travelling Salesman Problem (TSP):

Given a set of cities and the distance between every pair of cities, the problem is to
find the shortest possible route that visits every city exactly once and returns to the
starting point. Note the difference between Hamiltonian Cycle and TSP. The
Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly
once. Here we know that Hamiltonian Tour exists (because the graph is complete) and
in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian
Cycle.

For example, consider the graph shown in the figure on the right side. A TSP tour in
the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem
is a famous NP-hard problem. There is no polynomial-time know solution for this
problem. The following are different solutions for the traveling salesman problem.
Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate the cost of every permutation and keep track of the minimum cost
permutation.
4) Return the permutation with minimum cost.
Time Complexity: ?(n!)
Dynamic Programming:
Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and
ending point of output. For every other vertex I (other than 1), we find the minimum
cost path with 1 as the starting point, I as the ending point, and all vertices appearing
exactly once. Let the cost of this path cost (i), and the cost of the corresponding Cycle
would cost (i) + dist(i, 1) where dist(i, 1) is the distance from I to 1. Finally, we return
the minimum of all [cost(i) + dist(i, 1)] values. This looks simple so far.
Now the question is how to get cost(i)? To calculate the cost(i) using Dynamic
Programming, we need to have some recursive relation in terms of sub-problems.
Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex
in set S exactly once, starting at 1 and ending at i. We start with all subsets of size 2
and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for
all subsets S of size 3 and so on. Note that 1 must be present in every subset.
If size of S is 2, then S must be {1, i},
C(S, i) = dist(1, i)
Else if size of S is greater than 2.
C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j !=
i and j != 1.
Below is the dynamic programming solution for the problem using top down
recursive+memoized approach:-
For maintaining the subsets we can use the bitmasks to represent the remaining nodes
in our subset. Since bits are faster to operate and there are only few nodes in graph,
bitmasks is better to use.
For example: –
10100 represents node 2 and node 4 are left in set to be processed
010010 represents node 1 and 4 are left in subset.
NOTE:- ignore the 0th bit since our graph is 1-based
Output
The cost of most efficient tour = 80
Time Complexity : O(n2*2n) where O(n* 2n) are maximum number of unique
subproblems/states and O(n) for transition (through for loop as in code) in every
states.
Auxiliary Space: O(n*2n), where n is number of Nodes/Cities here.
For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t
have nth in them. Using the above recurrence relation, we can write a dynamic
programming-based solution. There are at most O(n*2n) subproblems, and each one
takes linear time to solve. The total running time is therefore O(n2*2n). The time
complexity is much less than O(n!) but still exponential. The space required is also
exponential. So this approach is also infeasible even for a slightly higher number of
vertices. We will soon be discussing approximate algorithms for the traveling
salesman problem.

Heuristic techniques
In this article, we are going to discuss Heuristic techniques along with some
examples that will help you to understand the Heuristic techniques more clearly.

What is Heuristics?
A heuristic is a technique that is used to solve a problem faster than the classic
methods. These techniques are used to find the approximate solution of a problem
when classical methods do not. Heuristics are said to be the problem-solving
techniques that result in practical and quick solutions.

Heuristics are strategies that are derived from past experience with similar problems.
Heuristics use practical methods and shortcuts used to produce the solutions that
may or may not be optimal, but those solutions are sufficient in a given limited
timeframe.

History
Psychologists Daniel Kahneman and Amos Tversky have developed the study of
Heuristics in human decision-making in the 1970s and 1980s. However, this concept
was first introduced by the Nobel Laureate Herbert A. Simon, whose primary
object of research was problem-solving.

Why do we need heuristics?

Heuristics are used in situations in which there is the requirement of a short-term
solution. On facing complex situations with limited resources and time, Heuristics can
help the companies to make quick decisions by shortcuts and approximated
calculations. Most of the heuristic methods involve mental shortcuts to make
decisions on past experiences.

The heuristic method might not always provide us the finest solution, but it is
assured that it helps us find a good solution in a reasonable time.

Based on context, there can be different heuristic methods that correlate with the
problem's scope. The most common heuristic methods are - trial and error,
guesswork, the process of elimination, historical data analysis. These methods involve
simply available information that is not particular to the problem but is most
appropriate. They can include representative, affect, and availability heuristics.

AD

AD

Heuristic search techniques in AI (Artificial

Intelligence)
We can perform the Heuristic techniques into two categories:

Direct Heuristic Search techniques in AI

It includes Blind Search, Uninformed Search, and Blind control strategy. These search
techniques are not always possible as they require much memory and time. These
techniques search the complete space for a solution and use the arbitrary ordering of
operations.

The examples of Direct Heuristic search techniques include Breadth-First Search (BFS)
and Depth First Search (DFS).

Weak Heuristic Search techniques in AI

It includes Informed Search, Heuristic Search, and Heuristic control strategy. These
techniques are helpful when they are applied properly to the right types of tasks.
They usually require domain-specific information.

The examples of Weak Heuristic search techniques include Best First Search (BFS) and
A*.

Before describing certain heuristic techniques, let's see some of the techniques listed
below:

o Bidirectional Search
 o A* search
o Simulated Annealing
o Hill Climbing
o Best First search
o Beam search

First, let's talk about the Hill climbing in Artificial intelligence.

Hill Climbing Algorithm

It is a technique for optimizing the mathematical problems. Hill Climbing is widely
used when a good heuristic is available.

It is a local search algorithm that continuously moves in the direction of increasing

elevation/value to find the mountain's peak or the best solution to the problem. It
terminates when it reaches a peak value where no neighbor has a higher value.
Traveling-salesman Problem is one of the widely discussed examples of the Hill
climbing algorithm, in which we need to minimize the distance traveled by the
salesman.

It is also called greedy local search as it only looks to its good immediate neighbor
state and not beyond that. The steps of a simple hill-climbing algorithm are listed
below:

AD

AD

Step 1: Evaluate the initial state. If it is the goal state, then return success and Stop.

Step 2: Loop Until a solution is found or there is no new operator left to apply.

Step 3: Select and apply an operator to the current state.

Step 4: Check new state:

If it is a goal state, then return to success and quit.

AD

AD

Else if it is better than the current state, then assign a new state as a current state.

Else if not better than the current state, then return to step2.
Step 5: Exit.

Best first search (BFS)

This algorithm always chooses the path which appears best at that moment. It is the
combination of depth-first search and breadth-first search algorithms. It lets us to
take the benefit of both algorithms. It uses the heuristic function and search. With
the help of the best-first search, at each step, we can choose the most promising
node.

Best first search algorithm:

Step 1: Place the starting node into the OPEN list.

Step 2: If the OPEN list is empty, Stop and return failure.

Step 3: Remove the node n from the OPEN list, which has the lowest value of h(n),
and places it in the CLOSED list.

Step 4: Expand the node n, and generate the successors of node n.

Step 5: Check each successor of node n, and find whether any node is a goal node or
not. If any successor node is the goal node, then return success and stop the search,
else continue to next step.

Step 6: For each successor node, the algorithm checks for evaluation function f(n)
and then check if the node has been in either OPEN or CLOSED list. If the node has
not been in both lists, then add it to the OPEN list.

Step 7: Return to Step 2.

A* Search Algorithm
A* search is the most commonly known form of best-first search. It uses the heuristic
function h(n) and cost to reach the node n from the start state g(n). It has combined
features of UCS and greedy best-first search, by which it solve the problem
efficiently.

It finds the shortest path through the search space using the heuristic function. This
search algorithm expands fewer search tree and gives optimal results faster.

Algorithm of A* search:

Step 1: Place the starting node in the OPEN list.

Step 2: Check if the OPEN list is empty or not. If the list is empty, then return failure
and stops.

Step 3: Select the node from the OPEN list which has the smallest value of the
evaluation function (g+h). If node n is the goal node, then return success and stop,
otherwise.

Step 4: Expand node n and generate all of its successors, and put n into the closed
list. For each successor n', check whether n' is already in the OPEN or CLOSED list. If
not, then compute the evaluation function for n' and place it into the Open list.

Step 5: Else, if node n' is already in OPEN and CLOSED, then it should be attached to
the back pointer which reflects the lowest g(n') value.

Step 6: Return to Step 2.

Examples of heuristics in everyday life

Some of the real-life examples of heuristics that people use as a way to solve a
problem:

o Common sense: It is a heuristic that is used to solve a problem based on the

observation of an individual.
 o Rule of thumb: In heuristics, we also use a term rule of thumb. This heuristic allows
an individual to make an approximation without doing an exhaustive search.
o Working backward: It lets an individual solve a problem by assuming that the
problem is already being solved by them and working backward in their minds to see
how much a solution has been reached.
o Availability heuristic: It allows a person to judge a situation based on the examples
of similar situations that come to mind.
o Familiarity heuristic: It allows a person to approach a problem on the fact that an
individual is familiar with the same situation, so one should act similarly as he/she
acted in the same situation before.
o Educated guess: It allows a person to reach a conclusion without doing an
exhaustive search. Using it, a person considers what they have observed in the past
and applies that history to the situation where there is not any definite answer has
decided yet.

AD
AD

Types of heuristics
There are various types of heuristics, including the availability heuristic, affect
heuristic and representative heuristic. Each heuristic type plays a role in decision-
making. Let's discuss about the Availability heuristic, affect heuristic, and
Representative heuristic.

Availability heuristic
Availability heuristic is said to be the judgment that people make regarding the
likelihood of an event based on information that quickly comes into mind. On
making decisions, people typically rely on the past knowledge or experience of an
event. It allows a person to judge a situation based on the examples of similar
situations that come to mind.

Representative heuristic
It occurs when we evaluate an event's probability on the basis of its similarity with
another event.

Example: We can understand the representative heuristic by the example of product

packaging, as consumers tend to associate the products quality with the external
packaging of a product. If a company packages its products that remind you of a
high quality and well-known product, then consumers will relate that product as
having the same quality as the branded product.

So, instead of evaluating the product based on its quality, customers correlate the
products quality based on the similarity in packaging.

Affect heuristic
It is based on the negative and positive feelings that are linked with a certain
stimulus. It includes quick feelings that are based on past beliefs. Its theory is one's
emotional response to a stimulus that can affect the decisions taken by an individual.

When people take a little time to evaluate a situation carefully, they might base their
decisions based on their emotional response.

Example: The affect heuristic can be understood by the example of advertisements.

Advertisements can influence the emotions of consumers, so it affects the purchasing
decision of a consumer. The most common examples of advertisements are the ads
of fast food. When fast-food companies run the advertisement, they hope to obtain a
positive emotional response that pushes you to positively view their products.

If someone carefully analyzes the benefits and risks of consuming fast food, they
might decide that fast food is unhealthy. But people rarely take time to evaluate
everything they see and generally make decisions based on their automatic
emotional response. So, Fast food companies present advertisements that rely on
such type of Affect heuristic for generating a positive emotional response which
results in sales.

Limitation of heuristics
Along with the benefits, heuristic also has some limitations.

o Although heuristics speed up our decision-making process and also help us to solve
problems, they can also introduce errors just because something has worked
accurately in the past, so it does not mean that it will work again.
o It will hard to find alternative solutions or ideas if we always rely on the existing
solutions or heuristics.

Conclusion
That's all about the article. Hence, in this article, we have discussed the heuristic
techniques that are the problem-solving techniques that result in a quick and
practical solution. We have also discussed some algorithms and examples, as well as
the limitation of heuristics.