Unit III: Decrease-and-Conquer & Divide-and-Conquer:

Decrease-and-Conquer: Introduction, Insertion Sort, Topological Sorting.

Divide-and-Conquer: Introduction, Merge Sort, Quick Sort, Binary Search, Binary Tree traversals
and related properties.

Decrease-and-Conquer: Introduction
Decrease or reduce problem instance to smaller instance of the same problem and extend
solution. Conquer the problem by solving smaller instance of the problem.
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.
Variations of Decrease and Conquer:
There are three major variations of decrease-and-conquer:
1. Decrease by a constant
2. Decrease by a constant factor
3. Variable size decrease

Insertion Sort Algorithm :

To sort an array of size N in ascending order iterate over the array and compare
the current element (key) to its predecessor, if the key element is smaller than its
predecessor, compare it to the elements before. Move the greater elements one
position up to make space for the swapped element.

Insertion Sort Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive simple
steps by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Pseudocode
Algorithm: Insertion-Sort(A)
for j = 2 to A.length
key = A[j]
i=j–1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i -1
A[i + 1] = key

Working of Insertion Sort algorithm

Consider an example: arr[]: {12, 11, 13, 5, 6}

12 11 13 5 6

First Pass:
 initially, the first two elements of the array are compared in insertion sort.
12 11 13 5 6

 Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at
its correct position. Thus, swap 11 and 12.
 So, for now 11 is stored in a sorted sub-array.
11 12 13 5 6

Second Pass:
 Now, move to the next two elements and compare them
11 12 13 5 6

 Here, 13 is greater than 12, thus both elements seem to be in ascending order, hence,
no swapping will occur. 12 also stored in a sorted sub-array along with 11

Third Pass:
 Now, two elements are present in the sorted sub-array which are 11 and 12
 Moving forward to the next two elements which are 13 and 5
 11 12 13 5 6

 Both 5 and 13 are not present at their correct place so swap them
11 12 5 13 6

 After swapping, elements 12 and 5 are not sorted, thus swap again
11 5 12 13 6

 Here, again 11 and 5 are not sorted, hence swap again

5 11 12 13 6

 Here, 5 is at its correct position

Fourth Pass:
 Now, the elements which are present in the sorted sub-array are 5, 11 and 12
 Moving to the next two elements 13 and 6

5 11 12 13 6

 Clearly, they are not sorted, thus perform swap between both
5 11 12 6 13

 Now, 6 is smaller than 12, hence, swap again

5 11 6 12
13

 Here, also swapping makes 11 and 6 unsorted hence, swap again

5 11
6 12 13

 Finally, the array is completely sorted

Time Complexity: O(N^2)

Complexity Analysis of Insertion Sort:

Time Complexity of Insertion Sort
 The worst-case time complexity of the Insertion sort is O(N^2)
 The average case time complexity of the Insertion sort is O(N^2)
 The time complexity of the best case is O(N).
Space Complexity of Insertion Sort
The auxiliary space complexity of Insertion Sort is O(1)
Characteristics of Insertion Sort
 This algorithm is one of the simplest algorithms with a simple implementation
 Basically, Insertion sort is efficient for small data values
 Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are already partially
sorted.
Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of
vertices such that for every directed edge u-v, vertex u comes before v in the
ordering.
Note: Topological Sorting for a graph is not possible if the graph is not a DAG.

Depth-First Search Algorithm

Depth-First Search (DFS Algorithm) can be used for Topological Sort by visiting each
node in the graph and recursively visiting its unvisited neighbors. The nodes are added
to the output list in reverse order of their finishing times, which gives a valid topological
ordering.
Algorithm
The algorithm for Topological Sorting using Depth-First Search is as follows:
1. Create a Graph object with V vertices.

2. Add edges between vertices using the addEdge method.

3. Create a visited array of size V and initialize it to False.

4. Create an empty stack to store the topological sorting of the vertices.

5. For each vertex v in the graph:

I. If v is not visited, call the topologicalSort method with v, visited, and stack.

6. In the topologicalSort method:

I. Mark v as visited.

II. For each adjacent vertex i of v:

1. If i is not visited, call topologicalSort with i, visited, and stack.

III. Push v onto the stack.

7. Return the stack with the topological sorting of the vertices.

EXAMPLE:

Applications of Topological Sorting:

 Topological Sorting is mainly used for scheduling jobs from the given dependencies
among jobs.
 In computer science, applications of this type arise in:
 Instruction scheduling
 Ordering of formula cell evaluation when recomputing formula values in
spreadsheets
 Logic synthesis
 Determining the order of compilation tasks to perform in make files
 Data serialization
 Resolving symbol dependencies in linkers.
 Divide and Conquer

A divide and conquer algorithm is a strategy of solving a large problem by

1. breaking the problem into smaller sub-problems

2. solving the sub-problems, and

3. combining them to get the desired output.

To use the divide and conquer algorithm, recursion is used. Learn about recursion in
different programming languages:
 Recursion in Java
 Recursion in Python
 Recursion in C++

Advantages of Divide and Conquer Algorithm

 The complexity for the multiplication of two matrices using the naive method is O(n3),
whereas using the divide and conquer approach (i.e. Strassen's matrix multiplication)
is O(n2.8074). This approach also simplifies other problems, such as the Tower of Hanoi.
 This approach is suitable for multiprocessing systems.

 It makes efficient use of memory caches.

Divide and Conquer Applications

 Binary Search
 Merge Sort
 Quick Sort
 Strassen's Matrix multiplication

 Karatsuba Algorithm
 Merge Sort Algorithm

What Is a Merge Sort Algorithm?

Merge sort is one of the most efficient sorting algorithms. It is based on the divide-
and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until
each has only one item, then merges those sublists into a sorted list.

Merge Sort Algorithm:

Our task is to merge two subarrays A[p..q] and A[q+1..r] to create a sorted array A[p..r] .

So the inputs to the function are A, p, q and r

The merge function works as follows:

1. Create copies of the subarrays L <- A[p..q] and M <- A[q+1..r] .

2. Create three pointers i , j and k

a. i maintains current index of L , starting at 1

b. j maintains current index of M, starting at 1
c. k maintains the current index of A[p..q] , starting at p .
3. Until we reach the end of either L or M, pick the larger among the elements
from L and M and place them in the correct position at A[p..q]

4. When we run out of elements in either L or M, pick up the remaining elements and put
in A[p..q]
Merge Sort pseudocode:

Merge Sort Example: 1.

Example 2:

Lets consider an array arr[] = {38, 27, 43, 10}

 Initially divide the array into two equal halves:

Merge Sort: Divide the array into two halves

 These subarrays are further divided into two halves. Now they become array of unit
length that can no longer be divided and array of unit length are always sorted.

Merge Sort: Divide the subarrays into two halves (unit length subarrays here)

These sorted subarrays are merged together, and we get bigger sorted subarrays.
 Merge Sort: Merge the unit length subarrys into sorted subarrays

This merging process is continued until the sorted array is built from the smaller
subarrays.

Merge Sort: Merge the sorted subarrys to get the sorted array

The following diagram shows the complete merge sort process for an example array
{38, 27, 43, 10}.

Merge Sort Applications

 Inversion count problem

 External sorting

 E-commerce applications
 Quick Sort:
• It works well on large set of data.
• In this method, division is dynamically carried out.
• The three steps of quick sort are as follows:
Step by Step Process
In Quick sort algorithm, partitioning of the list is performed using following steps...

Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the
list).

Step 2 - Define two variables i and j. Set i and j to first and last elements of the list
respectively.

Step 3 - Increment i until list[i] > pivot then stop.

Step 4 - Decrement j until list[j] < pivot then stop.

Step 5 - If i < j then exchange list[i] and list[j].

Step 6 - Repeat steps 3,4 & 5 until i > j.

Step 7 - Exchange the pivot element with list[j] element.

Binary Search:
• Binary Search is an efficient searching method.
• While searching elements using this method, the most essential thing is that the
elements in the array should be sorted one.

Consider 10,20,30,40,50,60 & 70 and search 60

Comparison of Linear & Binary Search
 Tree traversal (Inorder, Preorder an Postorder)
In this article, we will discuss the tree traversal in the data structure. The term 'tree traversal'
means traversing or visiting each node of a tree. There is a single way to traverse the linear data
structure such as linked list, queue, and stack. Whereas, there are multiple ways to traverse a tree
that are listed as follows -

o Preorder traversal
o Inorder traversal
o Postorder traversal

So, in this article, we will discuss the above-listed techniques of traversing a tree. Now, let's start
discussing the ways of tree traversal.

Preorder traversal
This technique follows the 'root left right' policy. It means that, first root node is visited after that
the left subtree is traversed recursively, and finally, right subtree is recursively traversed. As the
root node is traversed before (or pre) the left and right subtree, it is called preorder traversal.

So, in a preorder traversal, each node is visited before both of its subtrees.

The applications of preorder traversal include -

o It is used to create a copy of the tree.

o It can also be used to get the prefix expression of an expression tree.

Algorithm

1. Until all nodes of the tree are not visited

2. Step 1 - Visit the root node
3. Step 2 - Traverse the left subtree recursively.
4. Step 3 - Traverse the right subtree recursively.
 We start from A, and following pre-order traversal, we first visit A itself and then move
to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes
are visited. The output of pre-order traversal of this tree will be −
A→B→D→E→C→F→G

Postorder traversal
This technique follows the 'left-right root' policy. It means that the first left subtree of the root
node is traversed, after that recursively traverses the right subtree, and finally, the root node is
traversed. As the root node is traversed after (or post) the left and right subtree, it is called
postorder traversal.

So, in a postorder traversal, each node is visited after both of its subtrees.

The applications of postorder traversal include -

o It is used to delete the tree.

o It can also be used to get the postfix expression of an expression tree.

Algorithm

1. Until all nodes of the tree are not visited

2. Step 1 - Traverse the left subtree recursively.
3. Step 2 - Traverse the right subtree recursively.
4. Step 3 - Visit the root node.
 We start from A, and following pre-order traversal, we first visit the left subtree B. B is also
traversed post-order. The process goes on until all the nodes are visited. The output of post-order
traversal of this tree will be −
D→E→B→F→G→C→A

Inorder traversal
This technique follows the 'left root right' policy. It means that first left subtree is visited after
that root node is traversed, and finally, the right subtree is traversed. As the root node is traversed
between the left and right subtree, it is named inorder traversal.

So, in the inorder traversal, each node is visited in between of its subtrees.
The applications of Inorder traversal includes -

o It is used to get the BST nodes in increasing order.

o It can also be used to get the prefix expression of an expression tree.

Algorithm

1. Until all nodes of the tree are not visited

2. Step 1 - Traverse the left subtree recursively.
3. Step 2 - Visit the root node.
4. Step 3 - Traverse the right subtree recursively.

We start from A, and following in-order traversal, we move to its left subtree B.B is also
traversed in-order. The process goes on until all the nodes are visited. The output of in-order
traversal of this tree will be −
D→B→E→A→F→C→G

Properties of binary trees

The following are the properties of the binary trees:
1. The minimum number of nodes at height h:

In any binary tree, the minimum number of nodes will be one more than the value
of height. This is the number of nodes required to construct a tree.
Formula:

1. Height = h.
2. The minimum number of nodes = h+1.
3. If h=3, then nodes will be 3+1= 4.

2. The maximum number of nodes at height h:

The maximum number of nodes that can be inserted in any binary tree of height h will be
equal to 2h- 1.

Formula:

1. Height = h.
2. Maximum nodes to inserted = 2h- 1.
3. If h= 3, then 23- 1.
4. 8 -1= 7.

Therefore, the maximum number of nodes to be inserted for the height of h=3 will be 7.

3. Total number of leaf nodes:

The number of leaf nodes in a binary tree is equal to the nodes with degree two, plus one.
Say a binary tree has two children. Then the total number of leaf nodes of that binary tree
will be one greater than the nodes having two children.

Total number of leaf nodes = Nodes with 2 children + 1

Example:

Here, the total number of leaf nodes (no child or a successor) is 3, and the leaf nodes are
E, F, and G.

Whereas the nodes with two children are 2. Node A and B have 2 children. Hence, this
proves the property.
ACBDEGF
4. The maximum number of nodes at any level:

In a binary tree, the maximum number of nodes gained by any level is equal to the power
of 2 for that level.

In a simpler words, the level is donated by n. Then, maximum nodes of that binary tree
will be 2n.

Example:

n = 2 then 22= 4.

Level 2 coverts the nodes (D, E, F, and G).

ABCDEFG
Binary tree with maximum number of nodes at any level
5. Minimum possible height or levels is equal to Log 2(N+1):

This property says that the minimum number of levels or a height of a binary tree is the
Log2 of (N+1). Here N represents the maximum number of nodes possessed by a binary
tree at the height h.

We have already discussed property 2 along with the example. Let's use that answer to
calculate the height h.

1. N = 7 (Using Property#2)
2. Log2 of (N+1) = Log2 of (7+1)
3. Log2(8) = 3