MODULE 2

Divide and Conquer Strategy

 Top-down technique for designing algorithms.

 Divides the problem into smaller sub problems and then composes
the partial solutions into the solutions of the original problem
General Strategy

1 Divide
2 Conquer
3 Combine
Contd..
• Algorithms based on Divide and Conquer:
 Merge Sort
 Quick Sort
 Binary Search
Merge Sort
• Sorting Problem: Sort a sequence of n elements into non-decreasing
order.

 Divide: Divide the n-element sequence to be sorted into two

subsequences of n/2 elements each
 Conquer: Sort the two subsequences recursively using merge sort.
 Combine: Merge the two sorted subsequences to produce the
sorted answer.
Example
Pseudocode/Algorithm/Analysis
• Given in detail as notes
Quicksort Algorithm
Given an array of n elements (e.g., integers):
• If array only contains one element, return
• Else
• pick one element to use as pivot.
• Partition elements into two sub-arrays:
• Elements less than or equal to pivot
• Elements greater than pivot
• Quicksort two sub-arrays
• Return results
Example
We are given array of n integers to sort:

40 20 10 80 60 50 7 30 100
Pick Pivot Element
There are a number of ways to pick the pivot element. In this
example, we will use the first element in the array:

40 20 10 80 60 50 7 30 100
Partitioning Array
Given a pivot, partition the elements of the array
such that the resulting array consists of:
1. One sub-array that contains elements >= pivot
2. Another sub-array that contains elements < pivot

The sub-arrays are stored in the original data array.

Partitioning loops through, swapping elements

below/above pivot.
pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 4 7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
Partition Result

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

Recursion: Quicksort Sub-arrays

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• What is best case running time?
Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• What is best case running time?
• Recursion:
1. Partition splits array in two sub-arrays of size n/2
2. Quicksort each sub-array
Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• What is best case running time?
• Recursion:
1. Partition splits array in two sub-arrays of size n/2
2. Quicksort each sub-array
Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• Best case running time: O(n log2n)
Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• Best case running time: O(n log2n)
• Worst case running time?
Quicksort: Worst Case
• Assume first element is chosen as pivot.
• Assume we get array that is already in order:

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

too_big_index too_small_index
 1. While data[too_big_index] <= data[pivot]
++too_big_index
2. While data[too_small_index] > data[pivot]
--too_small_index
3. If too_big_index < too_small_index
swap data[too_big_index] and data[too_small_index]
4. While too_small_index > too_big_index, go to 1.
5. Swap data[too_small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• Best case running time: O(n log2n)
• Worst case running time?
• Recursion:
1. Partition splits array in two sub-arrays:
• one sub-array of size 0
• the other sub-array of size n-1
2. Quicksort each sub-array
Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• Best case running time: O(n log2n)
• Worst case running time: O(n2)!!!
Quicksort Analysis
• Assume that keys are random, uniformly distributed.
• Best case running time: O(n log2n)
• Worst case running time: O(n2)!!!
• What can we do to avoid worst case?

Note: Detailed steps of Analysis given as notes

Improved Pivot Selection
Pick median value of three elements from data array:
data[0], data[n/2], and data[n-1].

Use this median value as pivot.

 Decrease-and-Conquer
1. Reduce problem instance to smaller instance of the same problem
2. Solve smaller instance
3. Extend solution of smaller instance to obtain solution to original
instance

• Can be implemented either top-down or bottom-up

• Also referred to as inductive or incremental approach
• 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.
• Extend solution of smaller instance to obtain solution to original
problem .

• Top-down approach : It always leads to the recursive

implementation of the problem.
• Bottom-up approach : It is usually implemented in iterative way,
starting with a solution to the smallest instance of the problem.
There are three major variations of decrease-and-conquer:
• Decrease by a constant
• Decrease by a constant factor
• Variable size decrease
 A topological sorting or topological ordering
of a
directed is a linear ordering of
graph, its vertices such that for
every directed edge uv from
vertex u to vertex v, u comes
Topological Sort before v in the ordering.
Define
 Done in a way that for every
Topological edge ab from vertex a to b, the
vertex a comes before the vertex b
sorting in the topological ordering.

algorithm
In other words, the topological
sorting of a Directed Acyclic
Technically Graph is linear ordering of all of
its vertices.
 ALGORITHM FOR TOPOLOGICAL SORT

- Compute the indegrees of all vertices

- Find a vertex U with indegree 0 and print it (store it in the

ordering)If there is no such vertex then there is a cycle and the
vertices cannot be ordered. Stop.

- Remove U and all its edges (U,V) from the graph.

- Update the indegrees of the remaining vertices.

- Repeat steps 2 through 4 while there are vertices to be processed

 1 2

Representation
3 4 5

Consider this 6 7
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1 6 7

1
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1, 2 6 7

1 2
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1, 2, 5 6 7

1 2 5
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1, 2, 5, 4 6 7

1 2 5 4
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1, 2, 5, 4, 3 6 7

1 2 5 4 3
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1, 2, 5, 4, 3, 6 6 7

1 2 5 4 3 6
 Indegrees
1 2

0: 1,2
1:5
2: 3, 6,7
3 4 5

3:4
- Select 1, 2, 5, 4, 3, 6, 7 6 7

1 2 5 4 3 6 7
 1 2

Topologicall 3 4 5

y sorted
6 7

1 2 5 4 3 6 7
1. Complexity of an algorithm
Initialize In-Degree array: O(|V| + |E|)
Initialize Queue with In-Degree 0 vertices: O(|V|)
Dequeue and output vertex:
› |V| vertices, each takes only O(1) to dequeue and
output: O(|V|)
Reduce In-Degree of all vertices adjacent to a vertex
and Enqueue any In-Degree 0 vertices:
› O(|E|)
For input graph G=(V,E) run time = O(|V| + |E|)
Linear time
 Transform and Conquer
• Two-step process:
• Step 1: Modify problem instance to something easier to solve
• Step 2: Conquer

• Three major variations

• Instance Simplification: Transform to a simpler or more convenient instance of the same
problem
• Representation Change: Transform to a different representation of the same instance
• Problem Reduction: Transform to an instance of a different problem for which you know
an efficient algorithm
What is Transform and Conquer ?
1. Presorting

Simpler instance
Problem’s Or
instance Another representation Solution
Or
Another problem’s instance

1. Heapsort
1. Reduction to Optimization Problems
2. Binary Exponentiation
2. Reduction to Graph Problems
 Transform. & Conq.: Heapsort
• Another O(nlgn) sorting algorithm
• Uses the data structure called “Heap”
• It transforms an array into a Heap and then sorting becomes very easy
• A “heap” can be described as a binary tree, with one key per node,
provided the following two conditions are met:
• Shape property: Binary tree is essentially complete, all levels are full except
possibly the last level, where only some right most leaves may be missing
• Parental dominance (or heap property): key in each node is greater than or
equal to the keys in its children (considered automatically satisfied for the
leaves)
This is actually the “max heap”,
There is a corresponding “min heap”…
Trns. & Conq.: Heap
Shape and Heap 10
properties…
10
5 7
5 7
Is it a Heap ? 2 1
4 2 1

10

5 7

6 2 1
 Trns. & Conq.: Heap
10

8 7

5 2 1 6
ALGORITHM Parent(i)
return 𝑖 Τ2
3 5 1
ALGORITHM Left(i)
return 2i
index: 0 1 2 3 4 5 6 7 8 9
ALGORITHM 10
Right(i)
value: 10 8 7 5 2 1 6 3 1 +1
5 return2𝑖

parents leaves
 Trns. & Conq.: Heap
one parent
Heapify
COMPLEXITY
• For the heapify step, we're examining every item in the tree and
moving it downwards until it's larger than its children. Since our tree
height is O(log(n)), we could do up to O(log(n)) moves
• After transforming the tree into a heap, we remove all nn elements
from it—one item at a time.
• Doing n remove operations will be O(nlog(n)) time.