Design And Analysis of Algorithms[15CS53T] 2020-21
UNIT -5
DECREASE-AND-CONQUER
1.1 Introduction
The decrease-and-conquer technique is based on exploiting the relationship between a
solution to a given instance of a problem and a solution to its smaller instance.
There are 3 major variations of decrease and conquer.
1. Decrease by a Constant.
2. Decrease by a Constant factor.
3. Variable size Decrease.
1. Decrease by a Constant:
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
decrease-by-one idea is illustrated in below Figure.
Fig.4.1: Decrease-(by one)-and-conquer technique.
2. Decrease by a Constant Factor:
The decrease-by-a-constant-factor technique suggests reducing a problem instance by the same
constant factor on each iteration of the algorithm. In most applications, this constant factor is
equal to two. The decrease-by-half idea is illustrated in below Figure.
Dept. of CSE, Govt. Polytechnic-Kudligi[174] Page 1
Design And Analysis of Algorithms[15CS53T] 2020-21
Fig.4.2: Decrease-(by half)-and-conquer technique.
3. Variable size Decrease:
The Size reduction patterns various from one iteration of an algorithm to other
iteration of an algorithm.
1.2 Insertion Sort
It is a simple Sorting algorithm which sorts the array by shifting elements one by one.
Insertion sort works as follows
1. Set the marker for the sorted section after the first element in an array.
2. Select the first unsorted element
3. Compare the sorted section element with unsorted section element and swap those
elements if the condition is true
4. Move the marker to the right position of sorted section.
5. Repeat the steps 3 and 4 until the unsorted section is empty.
Dept. of CSE, Govt. Polytechnic-Kudligi[174] Page 2
Design And Analysis of Algorithms[15CS53T] 2020-21
Insertion sort is clearly based on a recursive idea, it is more efficient to implement this
algorithm iteratively. As shown in below Figure, starting with A[1] and ending with A[n −
1], A[i] is inserted in its appropriate place among the first i elements of the array that have
been already sorted.
Here is Pseudocode of this algorithm:
The operation of the algorithm is illustrated in below Figure:
Dept. of CSE, Govt. Polytechnic-Kudligi[174] Page 3
Design And Analysis of Algorithms[15CS53T] 2020-21
1.3 Topological Sorting
A directed graph that does not have cycle is called a Directed Acyclic Graph (DAG)
An ordering of the vertices in a directed acyclic graph, such that if there in a path from u to
v, then v is appears after u in the ordering. This is called topology sort.
There are two types commonly by used algorithm for sorting the vertices using topological
sort.
1. DFS
2. Source Removal Algorithm.
“A directed graph has a topological order if and only if it is a DAG.”
1. DFS Method: perform a DFS traversal and note the order in which vertices become dead-
ends. Reversing this order yields a solution to the topological sorting problem. It is illustrated in
below figure:
2. Source Removal Algorithm: is based on a direct implementation of the decrease-(by one)-
and-conquer technique: repeatedly, identify in a remaining digraph a source, which is a vertex
with no incoming edges, and delete it along with all the edges outgoing from it. The order in
which the vertices are deleted yields a solution to the topological sorting problem. It is
illustrated in below figure:
Dept. of CSE, Govt. Polytechnic-Kudligi[174] Page 4
Design And Analysis of Algorithms[15CS53T] 2020-21
Dept. of CSE, Govt. Polytechnic-Kudligi[174] Page 5