Module 2- Important Questions and Answers, DAA (21CS42)
Decrease and Conquer Approach: Introduction, Insertion sort, Graph searching algorithms,
Topological Sorting. It’s efficiency analysis.
Decrease and Conquer Approach: Introduction
Decrease and conquer is a technique used to solve problems by reducing the size of the input data at each
step of the solution process. This technique is similar to divide-and-conquer, in that it breaks down a
problem into smaller subproblems, but the difference is that in decrease-and-conquer, the size of the input
data is reduced at each step. The technique is used when it’s easier to solve a smaller version of the
problem, and the solution to the smaller problem can be used to find the solution to the original problem.
Decrease & conquer is a general algorithm design strategy based on exploiting the relationship between a
solution to a given instance of a problem and a solution to a smaller instance of the same problem. The
exploitation can be either top-down (recursive) or bottom-up (non-recursive).
The major variations of decrease and conquer are
1. Decrease by a constant :(usually by 1):
➢ a. insertion sort
➢ b. graph traversal algorithms (DFS and BFS)
➢ c. topological sorting
2. Decrease by a constant factor (usually by half)
➢ a. binary search and bisection method
3. Variable size decrease
➢ a. Euclid’s algorithm
In the decrease-by-a-constant variation, the size of an instance is reduced by the same constant on each
iteration of the algorithm. Typically, this constant is equal to one.
The relationship between a solution to an instance of size n and an instance of size n-1 is obtained by the
obvious formula: an= a n-1*a.
So the function f (n) =a" can be computed either "top down" by using its recursive definition or "bottom up"
by multiplying a by itself n - 1 times.
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Decrease (by one)-and-conquer technique
The decrease-by-a-constant-factor technique suggests reducing a problem's instance by the same constant
factor on each iteration of the algorithm. In most applications, this constant factor is equal to two.
If the instance of size n is to compute an, the instance of half its size will be to compute an/2. with the obvious
relationship between the two: a"= (an/2) 2.
If we compute an recursively according to above formula (5.2) and measure the algorithm's efficiency by the
number of multiplications, we should expect the algorithm to be in O (log n) because, on each iteration, the
size is reduced by at least one half at the expense of no more than two multiplications.
Note a difference between this algorithm and the one based on the divide and-conquer idea of solving two
instances of the exponentiation problem of size n/2:
The algorithm based on formula (5.3) is inefficient (why?), whereas the one based on (5.2) is much faster
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Decrease (by half)-and-conquer technique
In the Variable-Size-Decrease variety of decrease-and-conquer, a size reduction pattern varies from one
iteration of an algorithm to another. Euclid's algorithm for computing the greatest common divisor provides a
good example of such a situation. Recall that, this algorithm is based on the formula.
Insertion Sort:
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
In the worst case, insertion sort makes number of comparisons :
For sorted arrays, the number of key comparisons is
Insertion sort makes on average half as many comparisons as on decreasing arrays.
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Graph searching algorithms:
Depth-First Search
Depth-first search starts visiting vertices of a graph at an arbitrary vertex by marking it as having been visited.
On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. (If
there are several such vertices. a tie can be resolved arbitrarily. As a practical matter, which of the adjacent
unvisited candidates is chosen is dictated by the data structure representing the graph. In our examples, we
will always break ties by the alphabetical order of the vertices.) This process continues until a dead end-a
vertex with no adjacent unvisited vertices-is encountered. At a dead end, the algorithm backs up one edge to
the vertex it came from and tries to continue visiting unvisited vertices from there. The algorithm eventually
halts after backing up to the starting vertex, with the latter being a dead end. By then, all the vertices in the
same connected component as the starting vertex have been visited. If unvisited vertices still remain, the
depth-first search must be restarted at any one of them.
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
2. Example:
3. Example:
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Breadth-First Search
If depth-first search is a traversal for the brave (the algorithm goes as far from "home" as it can), breadth-first
search is a traversal for the cautious. It proceeds in a concentric manner by visiting first all the vertices that are
adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on, until all the vertices in the
same connected component as the starting vertex are visited. If there still remain unvisited vertices, the algorithm has to
be restarted at an arbitrary vertex of another connected component of the graph.
It is convenient to use a queue (note the difference from depth-first search!) to trace the operation of breadth-
first search. The queue is initialized with the traversal's starting vertex, which is marked as visited. On each
iteration, the algorithm identifies all unvisited vertices that are adjacent to the front vertex, marks them as
visited, and adds them to the queue; after that, the front vertex is removed from the queue.
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
Module 2- Important Questions and Answers, DAA (21CS42)
Department of Artificial Intelligence & Machine Learning, GMIT, Davangere
