Design and Analysis of

Algorithms
(CSC-314)

B.Sc. CSIT
 Unit-3:Divide and Conquer Algorithms
Introduction:
●
In computer science, divide and conquer is an algorithm
design paradigm.
●
A divide-and-conquer algorithm recursively breaks down
a problem into two or more sub-problems of the same or
related type, until these become simple enough to be
solved directly.
●
The solutions to the sub-problems are then combined to
give a solution to the original problem.
●
The divide-and-conquer technique is the basis of efficient
algorithms for many problems, such as sorting (e.g.,
quicksort, merge sort).

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Introduction:
●
This technique can be divided into the following three
parts:
– Divide: This involves dividing the problem into smaller
sub-problems.
– Conquer: Solve sub-problems by calling recursively
until solved.
– Combine: Combine the sub-problems to get the final
solution of the whole problem.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Introduction:
●
This technique can be divided into the following three
parts:
– Divide: This involves dividing the problem into smaller
sub-problems.
– Conquer: Solve sub-problems by calling recursively
until solved.
– Combine: Combine the sub-problems to get the final
solution of the whole problem.

Design and Analysis of Algorithms (CSC-314)

Unit-3:Divide and Conquer Algorithms

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Algorithm:
Algorithm D and C (P) {
if small(P)
then return S(P)
else {
– divide P into smaller instances P1 ,P2 .....Pk
– Apply D and C to each sub problems
– Return combine (D and C(P1)+ D and C(P2)+.......+D and
C(Pk))
}
}

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Let a recurrence relation is expressed as

T(n)= Θ(1), if n<=C

aT(n/b) + D(n)+ C(n) ,otherwise

●
Here,
– n=input size
– a = no. of sub-problems
– n/b = input size of the sub-problems

Design and Analysis of Algorithms (CSC-314)

Unit-3:Divide and Conquer Algorithms

Design and Analysis of Algorithms (CSC-314)

Unit-3:Divide and Conquer Algorithms

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Some of the specific computer algorithms are based on
the Divide & Conquer approach:
– Maximum and Minimum Problem
– Binary Search
– Sorting (merge sort, quick sort)
– Tower of Hanoi...etc.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Some Applications of Divide and Conquer Approach:
●
Following algorithms are based on the concept of the Divide and
Conquer Technique:
●
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.
●
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.
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Some Applications of Divide and Conquer Approach:
●
Following algorithms are based on the concept of the
Divide and Conquer Technique:
●
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.
●
Closest Pair of Points: It is a problem of computational
geometry. This algorithm emphasizes finding out the
closest pair of points in a metric space, given n points,
such that the distance between the pair of points should
be minimal.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Some Applications of Divide and Conquer Approach:
●
Following algorithms are based on the concept of the Divide
and Conquer Technique:
●
Strassen's Algorithm: It is an algorithm for matrix multiplication,
which is named after Volker Strassen. It has proven to be much
faster than the traditional algorithm when works on large matrices.
●
Cooley-Tukey Fast Fourier Transform (FFT) algorithm: The
Fast Fourier Transform algorithm is named after J. W. Cooley and
John Turkey. It follows the Divide and Conquer Approach and
imposes a complexity of O(nlogn).
●
Karatsuba algorithm for fast multiplication: It is one of the
fastest multiplication algorithms of the traditional time, invented by
Anatoly Karatsuba in late 1960 and got published in 1962. It
multiplies two n-digit numbers in such a way by reducing it to at
most single-digit.
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Some Applications of Divide and Conquer Approach:
●
Following algorithms are based on the concept of the Divide
and Conquer Technique:
●
Strassen's Algorithm: It is an algorithm for matrix multiplication,
which is named after Volker Strassen. It has proven to be much
faster than the traditional algorithm when works on large matrices.
●
Cooley-Tukey Fast Fourier Transform (FFT) algorithm: The
Fast Fourier Transform algorithm is named after J. W. Cooley and
John Turkey. It follows the Divide and Conquer Approach and
imposes a complexity of O(nlogn).
●
Karatsuba algorithm for fast multiplication: It is one of the
fastest multiplication algorithms of the traditional time, invented by
Anatoly Karatsuba in late 1960 and got published in 1962. It
multiplies two n-digit numbers in such a way by reducing it to at
most single-digit.
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
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.
●
It is more proficient than that of its counterpart Brute Force technique.
●
Since these algorithms inhibit parallelism, it does not involve any
modification and is handled by systems incorporating parallel
processing

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
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.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
What is Search?
●
Search is a utility that enables its user to find documents,
files, media, or any other type of data held inside a
database.
●
Search works on the simple principle of matching the
criteria with the records and displaying it to the user. In
this way, the most basic search function works.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Searching Algorithms:
●
In computer science, a search algorithm is an algorithm
which solves a search problem.
●
Search algorithms work to retrieve information stored
within some data structure, or calculated in the search
space of a problem domain, either with discrete or
continuous values.
●
Types of algorithms:
– Linear (we have discussed in unit 2)
– binary, and
– hashing

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Binary search:
●
Binary search, also known as half-interval search or
logarithmic search or binary chop is a search algorithm
that finds the position of a target value within a sorted
array.
●
A binary search is an advanced type of search algorithm
that finds and fetches data from a sorted list of items.
●
Its core working principle involves dividing the data in the
list to half until the required value is located and
displayed to the user in the search result.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Binary search:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
How Binary Search Works?
The binary search works in the following manner:
●
The search process initiates by locating the middle
element of the sorted array of data.
●
After that, the key value is compared with the element:
– If it is the desired value then the search is successful
– If the key value is smaller than the search only in first
half of the array.
– In case the key value is greater than searching is
carried in second half of the array.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
●
Pseudo code:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Analysis:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Analysis:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Analysis:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Analysis:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Analysis:

Design and Analysis of Algorithms (CSC-314)

Unit-3:Divide and Conquer Algorithms

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
The above image illustrates the following:
●
You have an array of 10 digits, and the element 59 needs to be found.
●
All the elements are marked with the index from 0 – 9. Now, the middle of
the array is calculated. To do so, you take the left and rightmost values of
the index and divide them by 2.The result is 4.5, but we take the floor
value. Hence the middle is 4.
●
The algorithm drops all the elements from the middle (4) to the lowest
bound because 59 is greater than 24, and now the array is left with 5
elements only.
●
Now, 59 is greater than 45 and less than 63. The middle is 7. Hence the
right index value becomes middle – 1, which equals 6, and the left index
value remains the same as before, which is 5.
●
At this point, you know that 59 comes after 45. Hence, the left index,
which is 5, becomes mid as well.
●
These iterations continue until the array is reduced to only one element, or
the item to be found becomes the middle of the array.
Design and Analysis of Algorithms (CSC-314)
Unit-3:Divide and Conquer Algorithms

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
The above image illustrates the following:
●
You have an array of sorted values ranging from 2 to 20
and need to locate 18.
●
The average of the lower and upper limits is (l + r) / 2 = 4.
The value being searched is greater than the mid which
is 4.
●
The array values less than the mid are dropped from
search and values greater than the mid-value 4 are
searched.
●
This is a recurrent dividing process until the actual item
to be searched is found.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm:
●
The Max-Min Problem in algorithm analysis is finding the
maximum and minimum value in an array.
●
To find the maximum and minimum numbers in a given
array numbers [ ] of size n, the following algorithm can be
used.
– First we are representing the naive method and
– then we will present divide and conquer approach.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Naïve Method:
●
Naïve method is a basic method to solve any problem. In this
method, the maximum and minimum number can be found
separately. To find the maximum and minimum numbers, the
following straightforward algorithm can be used.
Algorithm: Max-Min-Element (numbers[ ])
max := numbers[1]
min := numbers[1]
for i = 2 to n do
if numbers[i] > max then
max := numbers[i]
if numbers[i] < min then
min := numbers[i]
return (max, min)
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Naïve Method:
Analysis:
●
The number of comparison in Naive method is 2n – 2.
– So Time complexity O(n).

●
The number of comparisons can be reduced using the
divide and conquer approach.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Divide and Conquer Approach
●
In this approach, the array is divided into two halves.
●
Then using recursive approach maximum and minimum
numbers in each halves are found. Later, return the
maximum of two maxima of each half and the minimum
of two minima of each half.
●
In this given problem, the number of elements in an array
is y−x+1, where y is greater than or equal to x.
●
Max−Min(x,y) will return the maximum and minimum
values of an array numbers[x...y].

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Divide and Conquer Approach
Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Divide and Conquer Approach
Pseudo code:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Divide and Conquer Approach
Analysis:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Max-Min Algorithm: Divide and Conquer Approach
Examples:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort:
●
It is one of the well-known divide-and-conquer algorithm.
This is a simple and very efficient algorithm for sorting a
list of numbers.
●
It divides the input array into two halves, calls itself for
the two halves, and then merges the two sorted halves.
●
The merge() function is used for merging two halves. The
merge(arr, l, m, r) is a key process that assumes that
arr[l..m] and arr[m+1..r] are sorted and merges the two
sorted sub-arrays into one.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort:
To sort an array A[l . . r]:
●
Divide
– Divide the n-element sequence to be sorted into two
subsequences of n/2 elements each
●
Conquer
– Sort the subsequences recursively using merge sort.
When the size of the sequences is 1 there is nothing
more to do
●
Combine
– Merge the two sorted subsequences
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Merge Sort:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort: Pseudo code

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort:
●
Time Complexity:
– NO of sub problems=2
– Size of each subproblem =n/2
– Dividing cost is constant for each subproblems
– Merging cost is n
– So recurrence relations is:
●
T(n) =1 if n=1
●
T(n) = 2T(n/2)+O(n) if n>1
– Solving this we get, T(n)=O(nlogn)
●
Space complexity:
– Auxiliary Space taken is O(n)

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort: Examples
●
Let's consider an array with values {14, 7, 3, 12, 9, 11, 6,
12}
●
Below, we have a pictorial representation of how merge
sort will sort the given array.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort: Examples

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Merge Sort: Examples
In merge sort we follow the following steps:
●
We take a variable p and store the starting index of our
array in this. And we take another variable r and store the
last index of array in it.
●
Then we find the middle of the array using the formula (p +
r)/2 and mark the middle index as q, and break the array
into two subarrays, from p to q and from q + 1 to r index.
●
Then we divide these 2 subarrays again, just like we
divided our main array and this continues.
●
Once we have divided the main array into subarrays with
single elements, then we start merging the subarrays.
●
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Quick Sort:
●
QuickSort is a Divide and Conquer algorithm. It picks an
element as pivot and partitions the given array around
the picked pivot.
●
There are many different versions of quickSort that pick
pivot in different ways.
– Always pick first element as pivot.
– Always pick last element as pivot
– Pick a random element as pivot.
– Pick median as pivot.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:
●
Quick Sort is one of the different Sorting Technique which is
based on the concept of Divide and Conquer, just like merge
sort.
●
But in quick sort all the heavy lifting(major work) is done while
dividing the array into subarrays, while in case of merge sort, all
the real work happens during merging the subarrays.
●
In case of quick sort, the combine step does absolutely nothing.
●
It is also called partition-exchange sort. This algorithm divides
the list into three main parts:
– Elements less than the Pivot element
– Pivot element(Central element)
– Elements greater than the pivot element
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Quick Sort:
●
Divide
Partition the array A[l…r] into 2 subarrays A[l..m] and
A[m+1..r], such that each element of A[l..m] is smaller
than or equal to each element in A[m+1..r]. Need to find
index p to partition the array.
●
Conquer
Recursively sort A[p..q] and A[q+1..r] using Quicksort
●
Combine
Trivial: the arrays are sorted in place. No additional work
is required to combine them.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:
Technically, quick sort follows the below steps:
●
Step 1 − Make any element as pivot
●
Step 2 − Partition the array on the basis of pivot
●
Step 3 − Apply quick sort on left partition recursively
●
Step 4 − Apply quick sort on right partition recursively

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:
●
Pivot element can be any element from the array, it can be the first
element, the last element or any random element. In this tutorial,
we will take the rightmost element or the last element as pivot.
●
For example: In the array {52, 37, 63, 14, 17, 8, 6, 25}, we take 25
as pivot. So after the first pass, the list will be changed like this.
{6 8 17 14 25 63 37 52}
●
Hence after the first pass, pivot will be set at its position, with all
the elements smaller to it on its left and all the elements larger
than to its right. Now 6 8 17 14 and 63 37 52 are considered as
two separate sunarrays, and same recursive logic will be applied
on them, and we will keep doing this until the complete array is
sorted.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:Pseudo Code

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:
●
Time complexity:
– In Worst Case: The worst case occurs when the
partition process always picks greatest or smallest
element as pivot. If we consider partition strategy
where last element is always picked as pivot, the
worst case would occur when the array is already
sorted in increasing or decreasing order. Following is
recurrence for worst case.
T(n) = T(0) + T(n-1) + O(n) which is equivalent to
●
T(n) = T(n-1) + O(n)
– The solution of above recurrence is O(n2)

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort: Examples
Problem Statement:
●
Consider the following array: 50, 23, 9, 18, 61, 32

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:Examples

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:Examples
Step 1:
– Make any element as pivot: Decide any value to be the pivot from the list. For convenience of code,
we often select the rightmost index as pivot or select any at random and swap with rightmost.
Suppose for two values “Low” and “High” corresponding to the first index and last index respectively.
– In our case low is 0 and high is 5.
– Values at low and high are 50 and 32 and value at pivot is 32.
– Partition the array on the basis of pivot: Call for partitioning which rearranges the array in such a
way that pivot (32) comes to its actual position (of the sorted array). And to the left of the pivot, the
array has all the elements less than it, and to the right greater than it.
– In the partition function, we start from the first element and compare it with the pivot. Since 50 is
greater than 32, we don’t make any change and move on to the next element 23.
– Compare again with the pivot. Since 23 is less than 32, we swap 50 and 23. The array becomes 23,
50, 9, 18, 61, 32
– We move on to the next element 9 which is again less than pivot (32) thus swapping it with 50
makes our array as 23, 9, 50, 18, 61, 32.
– Similarly, for next element 18 which is less than 32, the array becomes 23, 9, 18, 50, 61, 32. Now 61
is greater than pivot (32), hence no changes.
– Lastly, we swap our pivot with 50 so that it comes to the correct position.
– Thus the pivot (32) comes at its actual position and all elements to its left are lesser, and all
elements to the right are greater than itself.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Quick Sort:Examples
Step 2:
●
The main array after the first step becomes
– 23, 9, 18, 32, 61, 50
Step 3:
●
Now the list is divided into two parts
– Sublist before pivot element
– Sublist after pivot element
Step 4:
●
Repeat the steps for the left and right sublists recursively. The
final array thus becomes
– 9, 18, 23, 32, 50, 61.
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Randomized Quick Sort:
●
The algorithm is called randomized if its behavior depends on
input as well as random value generated by random number
generator.
●
The beauty of the randomized algorithm is that no particular
input can produce worst-case behavior of an algorithm.
●
IDEA: Partition around a random element. Running time is
independent of the input order.
●
No assumptions need to be made about the input distribution.
No specific input elicits the worst-case behavior.
●
The worst case is determined only by the output of a random-
number generator. Randomization cannot
●
eliminate the worst-case but it can make it less likely!
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Randomized Quick Sort:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Randomized Quick Sort:

i.e. T(n) =O(n2)

Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Concept of Heap Data Structures:
●
Heap is a special tree-based data structure.
●
A binary tree is said to follow a heap data structure if
– it is a complete binary tree.
– All nodes in the tree follow the property that they are
greater than their children
●
i.e. the largest element is at the root and both its
children and smaller than the root and so on. Such a
heap is called a max-heap.
●
If instead, all nodes are smaller than their children, it is
called a min-heap

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Concept of Heap Data Structures:
●
Heap is a special tree-based data structure.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Array Representation of Heap:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Array Representation of Heap:
●
Why array based representation for Binary Heap?
●
Since a Binary Heap is a Complete Binary Tree, it can
be easily represented as an array and the array-based
representation is space-efficient.
●
If the parent node is stored at index I, the left child can
be calculated by 2 * I + 1 and the right child by 2 * I + 2
(assuming the indexing starts at 0).

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Array Representation of Heap:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Generally, Heaps can be of two types:
●
Max-Heap:
– In a Max-Heap the key present at the root node must be
greatest among the keys present at all of it’s children.
The same property must be recursively true for all sub-
trees in that Binary Tree.
●
Min-Heap:
– In a Min-Heap the key present at the root node must be
minimum among the keys present at all of it’s children.
The same property must be recursively true for all sub-
trees in that Binary Tree.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Generally, Heaps can be of two types:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Concept of Heap Data Structures:
The following example diagram shows Max-Heap and Min-
Heap.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Adding/Deleting Nodes
●
New nodes are always inserted at the bottom level (left
to right) and nodes are removed from the bottom level
(right to left).

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Operations on Heaps
●
Maintain/Restore the max-heap property
– MAX-HEAPIFY
●
Create a max-heap from an unordered array
– BUILD-MAX-HEAP
●
Sort an array in place
– HEAPSORT

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms

Maintaining the Heap Property

●
Suppose a node is smaller than a child and Left and
Right subtrees of i are max-heaps. To eliminate the
violation:
– Exchange with larger child
– Move down the tree
– Continue until node is not smaller than children

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Maintaining the Heap Property

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Maintaining the Heap Property

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Maintaining the Heap Property

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
How to “heapify” a tree?
●
The process of reshaping a binary tree into a Heap data
structure is known as ‘heapify’.
●
A binary tree is a tree data structure that has two child
nodes at max. If a node’s children nodes are ‘heapified’,
then only ‘heapify’ process can be applied over that
node.
●
A heap should always be a complete binary tree.
●
Starting from a complete binary tree, we can modify it to
become a Max-Heap by running a function called
‘heapify’ on all the non-leaf elements of the heap. i.e.
‘heapify’ uses recursion.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Algorithm for “heapify”:
heapify(array)
Root = array[0]
Largest = largest( array[0] , array [2 * 0 + 1]. array[2 * 0 + 2])
if(Root != Largest)
Swap(Root, Largest)

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Example

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heapify: Pseudo code:
Max-Heapify(A, i, n)
{
l = Left(i)
r = Right(i)
largest=l;
if l ≤ n and A[l] > A[largest]
largest = l
if r ≤ n and A[r] > A[largest]
largest = r
if largest !=i
exchange (A[i] , A[largest])
Max-Heapify(A, largest, n)
}
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Heapify:
●
Time Complexity Analysis:
– In the worst case Max-Heapify is called recursively h
times, where h is height of the heap and since each
call to the heapify takes constant time.
– Time complexity = O(h) = O(logn)

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Building a Heap:
●
To build a max-heap from any tree, we can thus start
heapifying each sub-tree from the bottom up and end up
with a max-heap after the function is applied to all the
elements including the root element.

●
Consider the following examples
– Given data sequence{4,1,3,2,16,9,10,14,8,7}
– Here we need to construct binary tree first and
– We need to carry out heapify operations on every non
leaf nodes to build the Max-heap.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Building a Heap:
– Here we need to construct binary tree first for the
given data {4,1,3,2,16,9,10,14,8,7}

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Building a Heap:
– Then We need to carry out heapify operations to build the Max-heap.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Building a Heap: Pseudo Code

Build-Max-Heap(A)
n = length[A]
for i ← n/2 downto 1
{
MAX-HEAPIFY(A, i, n)
}

– Time Complexity:
– Running time: Loop executes O(n) times and complexity of Heapify
is O(logn), therefore complexity of Build-Max-Heap is O(nlogn).

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort:
●
Heap sort is a comparison-based sorting technique based on Binary
Heap data structure.
●
It is similar to selection sort where we first find the minimum element and
place the minimum element at the beginning.
●
We repeat the same process for the remaining elements.
●
Steps involved to sort n elements:
– Build a max-heap from the array
– Swap the root (the maximum element) with the last element in the
array
– “Discard” this last node by decreasing the heap size
– Call Max-Heapify on the new root
– Repeat this process until only one node remains

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Example

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Example

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Example

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Example

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Example

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Examples (do at your own)
●
Sort the following elements using heap sort
– [1,4,2,7,3]
●
First construct the binary tree and construct the heap of recently constructed binary tree.
●
Then apply heap sort.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Heap Sort: Pseudo Code

●
Analysis:
– Building heap takes O(n)
– Loop executes n times
– Heapify operations takes O(logn)
– So total T(n)=O(nlogn)
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Order statistics
●
Order statistics are sample values placed in ascending order. The study of order
statistics deals with the applications of these ordered values and their functions.
●
Let’s say you had three weights:
– X1 = 22 kg, X2 = 44 kg, and X3 = 12 kg.
●
To get the order statistics (Yn), put the items in numerical increasing order:
– Y1 = 12 kg
– Y2 = 22 kg
– Y3 = 44 kg
●
The kth smallest X value is normally called the kth order statistic.
●
More formally,
– If X1, X2,…, Xn are random iid observations taken from a population with n
continuous observations, then
– the random variables Y1 < Y2 < …, < Yn denote the sample’s order
statistics.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Order statistics
●
The ith order statistic of a set of n elements is the ith smallest element.
For example, the minimum of a set of elements is the first order statistic
(i = 1), and the maximum is the nth order statistic (i = n).

●
Median order
●
A median, informally, is the "halfway point" of the set.
●
When n is odd, the median is unique, occurring at i = (n + 1)/2. When n
is even, there are two medians, occurring at i = n/2 and i = n/2 + 1.
●
Thus, regardless of the parity of n, medians occur at i = lower bound(n +
1)/2 and i = upper bound(n + 1)/2.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Brute Force Algorithm:
●
This is the most basic and simplest type of algorithm.
●
A Brute Force Algorithm is the straightforward approach to a problem
i.e., the first approach that comes to our mind on seeing the problem.
●
More technically it is just like iterating every possibility available to solve
that problem.
●
For Example:
– If there is a lock of 4-digit PIN.
– The digits to be chosen from 0-9 then the brute force will be trying all
possible combinations one by one like 0001, 0002, 0003, 0004, and
so on until we get the right PIN.
– In the worst case, it will take 10,000 tries to find the right
combination.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms

Brute Force Algorithm:

●
Below given are some features of the brute force algorithm are:
– It is an intuitive, direct, and straightforward technique of problem-
solving in which all the possible ways or all the possible solutions to
a given problem are enumerated.
– Many problems solved in day-to-day life using the brute force
strategy, for example exploring all the paths to a nearby market to
find the minimum shortest path.
– Arranging the books in a rack using all the possibilities to optimize
the rack spaces, etc.
– In fact, daily life activities use a brute force nature, even though
optimal algorithms are also possible.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms

Brute Force Algorithm:

●
A straightforward approach, usually based directly on the problem’s
statement and definitions of the concepts involved.
●
Examples:
1. Computing an (a > 0, n a non negative integer)
2. Computing n!
3. Multiplying two matrices
4. Searching for a key of a given value in a list

Design and Analysis of Algorithms (CSC-314)

Unit-3:Divide and Conquer Algorithms

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms

Brute Force Algorithm:

●
Brute force algorithm is a technique that guarantees solutions for
problems of any domain helps in solving the simpler problems and also
provides a solution that can serve as a benchmark for evaluating other
design techniques, but takes a lot of run time and inefficient.

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Selection in Expected Linear Time
●
The general selection problem appears more difficult than the simple
problem of finding a minimum, yet, surprisingly, the asymptotic running
time for both problems is the same: (n).
●
Here this approach is a divide-and-conquer algorithm for the selection
problem.
●
The algorithm RANDOMIZED-SELECT is modeled after the quicksort
algorithm. As in quicksort, the idea is to partition the input array
recursively.
●
But unlike quicksort, which recursively processes both sides of the
partition, RANDOMIZED-SELECT only works on one side of the
partition.
●
This difference shows up in the analysis: whereas quicksort has an
expected running time of (nlogn), the expected time of RANDOMIZED-
SELECT is (n2).

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Selection in Expected Linear Time
●
This problem is solved by using the “divide and conquer” method. The main
idea for this problem solving is to partition the element set as in Quick Sort
where partition is randomized one.
●
Pseudo Code:
RandSelect(A,l,r,i)
{
if(l = =r )
return A[p];
p = RandPartition(A,l,r);
k = p – l + 1;
if(i <= k)
return RandSelect(A,l,p-1,i);
else
return RandSelect(A,p+1,r,i - k);
}
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Analysis:
●
Since our algorithm is randomized algorithm no particular input is
responsible for worst case however the worst case running time of this
algorithm is O(n 2 ).
●
This happens if every time unfortunately the pivot chosen is always the
largest one (if we are finding minimum element).

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Analysis:
●
T(n)=O(n)

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Selection in Worst Case Linear Time algorithm
●
We now examine a selection algorithm whose running time is O(n) in the
worst case. Like RANDOMIZED-SELECT, the algorithm SELECT finds
the desired element by recursively partitioning the input array.
●
The idea behind the algorithm, however, is to guarantee a good split
when the array is partitioned.
●
SELECT uses the deterministic partitioning algorithm PARTITION from
quicksort, modified to take the element to partition around as an input
parameter.
●

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Selection in Worst Case Linear Time algorithm

●
Here, The n elements are represented by small circles, and each group
occupies a column.
●
The medians of the groups are whitened, and the median-of-medians x is
labeled. Arrows are drawn from larger elements to smaller, from which it
can be seen that 3 out of every group of 5 elements to the right of x are
greater than x, and 3 out of every group of 5 elements to the left of x are
less than x.
●
The elements greater than x are shown on a shaded background.
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Selection in Worst Case Linear Time algorithm
●
Algorithms:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Selection in Worst Case Linear Time algorithm
●
Analysis:
– Here at least half of the medians are <=x, since there are at least n/5 medians
– So (n/5)/2 medians are <=x, i.e. n/10 medians are<=x
– Since each medians contributes 3 elements which are<=x i.e. 3n/10 elements are
<=x
– So out of n elements 7n/10 elements are>=x
– Now recurrence relation is:

Design and Analysis of Algorithms (CSC-314)

 Unit-3:Divide and Conquer Algorithms
Assignment:
●
Discuss some implementation issues that may arise in
divide and conquer algorithms.
●
Trace the algorithms for the following array of elements
elements by using recursive approach of Min-Max
algorithms.
[6,5,3,8,11,2,99,35,7]
●
Trace for key =7 in [-1,5,6,7,18,20,25,27,39,91,119,121]
using binary search.
●
Introduce the concepts of partitioning and analyze the best,
average and worst case time complexity of quick sort
algorithm based on divide and conquer approach. Sort the
following data using quick sort: [5,3,2,6,4,1,3,7]
Design and Analysis of Algorithms (CSC-314)
 Unit-3:Divide and Conquer Algorithms
Assignment:
●
Sort the following elements using heap sort:
{4,1,3,2,16,9,10,14,8,7}

Design and Analysis of Algorithms (CSC-314)