Module 2: Divide and Conquer: Design and Analysis of Algorithms 18CS42

Design and Analysis of
Algorithms 18CS42
Module 2: Divide and Conquer
Suriya Prakash J
Dept. of Computer Science and
Engineering
SCE Bangalore
Module 2 –
Outline Divide
and
1. Conquer
General method
2. Recurrence equation
3. Algorithm: Binary search
4. Algorithm: Finding the maximum and
minimum
5. Algorithm: Merge sort
6. Algorithm: Quick sort
7. Algorithm: Strassen’s matrix multiplication
8. Advantages and Disadvantages
9. Decrease and Conquer Approach
10. Algorithm: Topological Sort
18CS42-Design and Analysis of 2
Algorithms
Module 2 –
Outline Divide
and Conquer
1. General method
minimum
18CS42-Design and Analysis of 3
Algorithms
Divide and
Conquer
18CS42-Design and Analysis of Feb-May 4

Algorithms 2020
Control Abstraction for Divide
&Conquer

Algorithms 2020
Module 2 –
Outline Divide
1. General method
and Conquer
minimum
Algorithms 2020
Recurrence equation for Divide and
Conquer
If the size of problem ‘p’ is n and the sizes of the
‘k’ sub problems are n1, n2 ….nk, respectively,
then
Where,
• T(n) is the time for divide and conquer method on
any input of size n and
• g(n) is the time to compute answer directly for
small inputs.
• The function f(n) is the time for dividing the
problem ‘p’ and combining the solutions to sub
problems.
Algorithms 2020
Recurrence equation for Divide and
Conquer
• Generally, an instance of size n can be divided
into b
instances of size n/b,
• Assuming n = bk ,
where f(n) is a function that accounts for the time

spent on dividing the problem into smaller ones and
on combining their solutions.

Algorithms 2020
Algorithms 2020
Algorithms 2020 0
Will be solved under
topic Stressens
Matrix Multiplication

Algorithms 2020
Solving recurrence relation
using
Master theorem
It states that, in recurrence equation T(n) = aT(n/b) +
f(n), If f(n)∈ Θ (nd ) where d ≥ 0 then
Analogous results hold for the Ο and Ω notations,

too. Example:
Here a = 2, b = 2, and d = 0; hence, since a >bd,

Algorithms 2020
Module 2 –
Outline Divide
1. General method
and Conquer
minimum
Harivinod 18CS42-Design and Analysis of Feb-May 13
N Algorithms 2020
Binary
Search
Problem definition:
• Let ai, 1 ≤ i ≤ n be a list of elements that are
sorted in non-decreasing order.
• The problem is to find whether a given element
x is present in the list or not.
– If x is present we have to determine a value j
(element’s position) such that aj=x.
– If x is not in the list, then j is set to zero.

N Algorithms 2020
Binary
Search
Solution:
Let P = (n, ai…al , x) denote an arbitrary instance of
search problem
- where n is the number of elements in the list,
- ai…al is the list of elements and
- x is the key element to be searched

N Algorithms 2020
Binary
Search
Pseudocode
Step 1: Pick an index q in the middle range [i, l] i.e. q =
⎣
(n +1)/2
⎦
and compare x with aq.
Step 2: if x = aq i.e key element is equal to mid
element, the problem is immediately solved.
Step 3: if x < aq in this case x has to be searched for
only in the sub-list ai, ai+1, ……, aq-1. Therefore problem
reduces to (q- i, ai…aq-1, x).
Step 4: if x > aq , x has to be searched for only in the
sub-list aq+1, ...,., al . Therefore problem reduces to
(l-i, aq+1…al, x).

N Algorithms 2020
Recursive Binary search
algorithm

N Algorithms 2020
Iterative binary
search

N Algorithms 2020
N Algorithms 2020
N Algorithms 2020 0
N Algorithms 2020
Analys
is
• Time Complexity Proof: Not
available in
Recurrence relation (for worst the notes !
case) T(n) = T(n/2) + c

N Algorithms 2020
Analys
is
Space Complexity
– Iterative Binary search: Constant memory space
– Recursive: proportional to recursion stack.
Pros
– Efficient on very big list,
– Can be implemented iteratively/recursively.
Cons
– Interacts poorly with the memory hierarchy
– Requires sorted list as an input
– Due to random access of list element, needs arrays
instead of linked list.

N Algorithms 2020
Module 2 –
Outline Divide
1. General method
and Conquer
minimum
N Algorithms 2020
Max
Min
Problem statement
• Given a list of n elements, the problem is to
find the maximum and minimum items.
A simple and straight forward algorithm to
achieve this is given below.

N Algorithms 2020
Straight Max Min (Brute Force
MaxMin)
• 2(n-1) comparisons in the best, average &
worst cases.
• By realizing the comparison of a[i]>max is
false, improvement in a algorithm can be
done.
– Hence we can replace the contents of the for
loop by,
If(a[i]>Max) then Max =
a[i]; Else if (a[i]< min)
min=a[i]
– On the average a[i] is > max half the time.
– So, the avg.
Harivinod
no. of comparison is 3n/2-1.
N Algorithms 2020
Algorithm based on D & C
strategy

N Algorithms 2020
18CS42-Design and Analysis of
Harivinod 28
Algorithms
N
Feb-May 2020
Exampl
e

Harivinod 29
Algorithms
N
Feb-May 2020
Analysis - Time
Complexity
Compared with the straight forward method

Harivinod (2n-2)
N
this method saves
Algorithms 25% in
Feb-May
30
2020
comparisons.
Module 2 –
Outline Divide
1. General method
and Conquer
minimum
N Algorithms 2020
Merge
Sort
• Merge sort is a perfect example of
divide-and conquer technique.
• It sorts a given array by
– dividing it into two halves,
– sorting each of them recursively, and
– then merging the two smaller sorted arrays into a
single sorted one.

N Algorithms 2020
Merge sort -
example

N Algorithms 2020
Merge Sort -
Example
Original Sorted Sequence
Sequence
18
1 26
2 32
3 6 43
4 15
1 9 1 1 6 9 15 18 26 32 43
8 6 2 3 5
18
1 26
2 32
3 6
6 43
4 15
1 9
9 1
1 6
6 1 26
2 32
3 1
1 99 15
1 434
8 6 2 3 5 8 6 2 5 3
118 226 32
3 6
6 443 115 9
9 11 18 26
1 2 6
6 3 15 43
1 4 1
1 99
8 6 2 3 5 8 6 32 2 5 3
18
1 26
2 32
3 6
6 43
4 15
1 99 11 18
1 26
2 32
3 6 43
4 15 9 1
1
8 6 2 3 5 8 6 2 1
3 5 9
1 2 3 6 4 1 9 1
18
8 26
6 32
2 6 43
3 15
5 9 1

N Algorithms 2020
Merge
Sort

N Algorithms 2020
How to implement merge? (Link to Animated
slides)
Merge – Example
A … 61 8 6 26 83 19 9 2642 324 42
43 … 2 3
k k k k k k k k k
L 66 8 8 2 26
32 R 11 9 9 42 42
4
32 ∞ 6 43 ∞ 3
i i i i i j j j j j
dc - 1

N Algorithms 2020
Merg
e

N Algorithms 2020
Analysi
s
• Basic operation - key comparison.
• Best Case, Worst Case, Average Case exists?
– Execution does not depend on the order of the data
– Best case and average case runtime are the same
as worst case runtime.
• Worst case:
– During key comparison, neither of the two arrays
becomes empty before the other one contains just
one element

N Algorithms 2020
Analysis – Worst
Case
• Assuming for simplicity that total number of elements
n is a power of 2, the recurrence relation for the
number of key comparisons C(n) is
• Cmerge(n) - the number of key comparisons performed

during the merging stage.
• At each step, exactly one comparison is made,
total comparisons are (n-1)

N Algorithms 2020
Analysi
s
• Here a = 2, b = 2, f (n) = n-1 = Θ (n) => d =

1.
• Therefore 2 = 21, case 2 holds in the master
theorem
• Cworst (n) = Θ (nd log n) = Θ (n1 log n) = Θ (n log
n)
• Therefore Cworst(n) = Θ (n log n)

N Algorithms 2020
Advantag
es
• Number of comparisons performed is nearly
optimal.
• For large n, the number of comparisons made
by this algorithm in the average case turns out
to be about 0.25n less and hence is also in Θ(n
log n).
• Mergesort will never degrade to O(n2)
• Another advantage of mergesort over quicksort
is its stability.
(A sorting algorithm is said to be stable if two objects with
equal keys appear in the same order in sorted output as
they appear in18CS42-Design
Harivinod
the input array to be sorted.
and Analysis of Feb-May
) 41
N Algorithms 2020
Limitation
s
• The principal shortcoming of mergesort is the
linear amount O(n) of extra storage the
algorithm requires.
• Though merging can be done in-place, the
resulting algorithm is quite complicated and of
theoretical interest only.

N Algorithms 2020
Variation
s• The algorithm can be implemented bottom
up by merging pairs of the array’s elements,
then merging the sorted pairs, and so on
– This avoids the time and space overhead of using a
stack to handle recursive calls.
• We can divide a list to be sorted in more than

two parts, sort each recursively, and then
merge them together.
– This scheme, which is particularly useful for sorting
files residing on secondary memory devices, is
called multiway mergesort.

N Algorithms 2020
Module 2 –
Outline Divide
1. General method
and Conquer
minimum
N Algorithms 2020
Quick
Sort
• It is a Divide and Conquer method
• Sorting happens in Divide stage itself.
• C.A.R. Hoare ( also known as Tony Hore),
prominent British computer scientist invented
quicksort.

N Algorithms 2020
Quick
Sort
• Quicksort divides (or partitions) array
according to the value of some pivot element
A[s]
• Divide-and-Conquer:
– If n=1 terminate (every one-element list is already
sorted)
– If n>1, partition elements into two; based on
pivot element

N Algorithms 2020
Quick
Sort

N Algorithms 2020
How do we
partition?
• There are several different strategies for
selecting a pivot and partitioning.
• We use the sophisticated method suggested
by
C.A.R. Hoare, the inventor of quicksort.
• Select the subarray’s first element: p = A[l].

• Now scan the subarray from both ends,
comparing the subarray’s elements to the
pivot.

N Algorithms 2020
How do we partition? (Link to animated
slides)
Example
We are given array of n integers to sort:
40 20 10 80 60 50
7 30 100

N Algorithms 2020
How do we
partition?

N Algorithms 2020
N Algorithms 2020
Analysi
s
• Basic Operation : Key Comparison
• Best case exists
– all the splits happen in the middle of
subarrays,
– So the depth of the recursion in log2n
– As per Master Theorem, Cbest(n) ∈ Θ(n

log2 n);

N Algorithms 2020
Analysi
s
• Worst Case
– Splits will be skewed to the extreme
– This happens if the input is already sorted
• In the worst case, partitioning always divides the size n
array into these three parts:
• A length one part, containing the pivot itself
• A length zero part, and
• A length n-1 part, containing everything else
• Recurring on the length n-1 part requires (in the worst
case) recurring to depth n-1

N Algorithms 2020
Analysi
s• Worst
Case

N Algorithms 2020
Analysi
s
Worst Case
• if A[0..n − 1] is a strictly increasing array and
we use A[0] as the pivot,
– the left-to-right scan will stop on A[1] while the
right-to- left scan will go all the way to reach A[0],
indicating the split at position 0
– n + 1 comparisons required
Total comparisons

N Algorithms 2020
Analysi
s
Average Case
• Let Cavg(n) be the average number of key
comparisons made by quicksort on a
randomly ordered array of size n.
• A partition can happen in any position s (0 ≤ s ≤
n−1)
• n+1 comparisons are required for partition.
• After the partition, the left and right subarrays
will have s and n − 1− s elements,
respectively.

N Algorithms 2020
Analysi
s
Average Case
• Assuming that the partition split can happen in
each position s with the same probability 1/n,
we get

N Algorithms 2020
Pros and
Cons
• Pros
– Good average case time complexity
• Cons
– It is not stable.
– It requires a stack to store parameters of
subarrays that are yet to be sorted.

N Algorithms 2020
Module 2 –
Outline Divide
1. General method
and Conquer
minimum
7. Algorithm: Strassen’s matrix
multiplication
N Algorithms 2020
Matrix
Multiplication
Direct Method:
• Suppose we want to multiply two n x n
matrices, A and B.
• Their product, C=AB, will be an n by n matrix
and will therefore have n2 elements.
• The number of multiplications involved in
producing the product in this way is Θ(n3)

N Algorithms 2020
Matrix
Multiplication
• Divide and Conquer method for Matrix
multiplication
• How many Multiplications?

• 8 multiplications for matrices of size n/2 x n/2 and 4
additions.
• Addition of two matrices takes O(n2) time. So the
time complexity can be written as T(n) = 8T(n/2) +
O(n2) which happen to be O(n3); same as the direct
method
N Algorithms 2020
Stressen’s matrix
multiplication
Multiplication of2 × 2 matrices:
• By using divide-and-conquer
approach we can reduce the
number of multiplications.
• Such an algorithm was published
by
V. Strassen in 1969.

N Algorithms 2020
Strassen’s matrix
multiplication
• The principal insight of the
algorithm
– product C of two 2 × 2 matrices A and
B
– with just seven multiplications
• This is accomplished by

N Algorithms 2020
Strassen’s matrix
multiplication

N Algorithms 2020
Analysi
s
• Recurrence relation (considering only
multiplication)

N Algorithms 2020
Analysis ( From T2: Horowitz
et al )

N Algorithms 2020
Module 2 –
Outline Divide
1.and Conquer
General method
minimum
10.HarivinodAlgorithm: Topological Sort
N Algorithms 2020
Advantages and Disadvantages of
Divide & Conquer
✔ Parallelism: Divide and conquer algorithms tend to
have a lot of inherent parallelism.
✔ Cache Performance: Once a sub-problem fits in the
cache, the standard recursive solution reuses the
cached data until the sub-problem has been
completely solved.
✔ It allows solving difficult and often impossible
looking problems like the Tower of Hanoi
X Recursion is slow
– sometimes it can become more complicated than a
basic iterative approach, the same sub problem
can occur many times. It is solved again.
N Algorithms 2020
Module 2 –
Outline Divide
and Conquer
1. General method
minimum

N Algorithms 2020
Decrease and Conquer
Approach
• There are three major variations of
decrease-and- conquer:
– decrease-by-a-constant, most often by one (e.g.,
insertion sort)
– decrease-by-a-constant-factor, most often by the
factor of two (e.g., binary search)
– variable-size-decrease (e.g., Euclid’s algorithm)

N Algorithms 2020
Topologocal
Sorting
• Graph, Digraph
• Adjacency matrix and adjacency
list
• DFS, BFS

N Algorithms 2020
Digrap
h
• A directed cycle in a digraph is a sequence of
three or more of its vertices that starts and
ends with the same vertex
• For example, a, b, a is a directed cycle in the
digraph in Figure given above.
• Conversely, if a DFS forest of a digraph has no
back edges, the digraph is a dag, an acronym
for directed acyclic graph.

N Algorithms 2020
Motivation for topological
sorting
• Consider a set of five required courses {C1, C2, C3,
C4, C5} a part-time student has to take in some
degree program.
• The courses can be taken in any order as long
as the following course prerequisites are met:
– C1 and C2 have no prerequisites,
– C3 requires C1 and C2,
– C4 requires C3, and
– C5 requires C3 and C4.
• The student can take only one course per term.
• In which order should the student take the courses?
This problem is
called
Harivinod 18CS42-Design topological
and Analysis of Feb-May 73
N Algorithms 2020
sorting.
Topological
Sort
• For topological sorting to be possible, a
digraph in question must be a DAG.
• There are two efficient algorithms that both
verify whether a digraph is a dag and, if it is,
produce an ordering of vertices that solves
the topological sorting problem.
– The first one is based on depth-first search
– the second is based on a direct application
of the decrease-by-one technique.

N Algorithms 2020
Topological Sorting based on
DFS
Method
1. Perform a DFS traversal and note the order in
which vertices become dead-ends
2. Reversing this order yields a solution to
the topological sorting problem,
provided, no back edge has been encountered
during the traversal.
If a back edge has been encountered, the digraph is
not a dag, and topological sorting of its vertices is
impossible.

N Algorithms 2020
N Algorithms 2020
Topological Sorting using
decrease-and-conquer technique:
Method: The algorithm is based on a direct
implementation of the decrease-(by
one)-and-conquer technique:
1. 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.
(If there are several sources, break the tie arbitrarily. If
there are none, stop because the problem cannot be
solved.)
2. The order in which the vertices are deleted
yields a solution to the topological sorting
N
problem.
Harivinod 18CS42-Design and Analysis of
Algorithms
Feb-May
2020
77
Illustratio
n

N Algorithms 2020
Applications of Topological
Sorting
• Observation: Topological sorting problem may
have several alternative solutions.
• Instruction scheduling in program compilation

• Cell evaluation ordering in spreadsheet
formulas,
• Resolving symbol dependencies in linkers.

N Algorithms 2020
Summar
y
• Divide and Conquer
– Recurrence equation
– Binary search
– Finding the maximum and minimum
– Merge sort
– Quick sort
– Strassen’s matrix multiplication
• Advantages and Disadvantages of

D&C
• Decrease and Conquer Approach

– Algorithm: 18CS42-Design
Harivinod
Topological Sort
and Analysis of Feb-May 80
N Algorithms 2020
Assignment-2 Due: Within 5 days
1. Solve the following recurrence relation by substitution

method. T(n) = 9T(n/3)+4n6, n≥3 and n is a power of 3
2. Discuss how quick-sort works to sort an array and trace
for the following dataset. Draw the tree of recursive calls
made.
65, 70, 75, 80, 85, 60, 55, 50, 45
3. What are the three major variations of decrease and
conquer technique? Explain with an example for each.
4. Apply Strassen's matrix multiplication to multiply following
matrices. Discuss method is better than direct matrix
multiplication method.

N Algorithms 2020
Extra Byte
1.Arrange +ve and –ve: Design an algorithm (using divide
and conquer) to rearrange elements of a given array of n
real numbers so that all its negative elements precede all
its positive elements. Your algorithm should be both time
efficient and space efficient.
2.: The Dutch national flag problem is to rearrange an

array of characters R, W, and B (red, white, and blue are
the colors of the Dutch national flag) so that all the R’s
come first, the W’s come next, and the B’s come last.
Design a linear in-place algorithm for this problem.

N Algorithms 2020

Module 2: Divide and Conquer: Design and Analysis of Algorithms 18CS42

Uploaded by

Copyright:

Available Formats

Module 2: Divide and Conquer: Design and Analysis of Algorithms 18CS42

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module 2: Divide and Conquer: Design and Analysis of Algorithms 18CS42

Uploaded by

Copyright:

Available Formats

Design and Analysis of

Module 2: Divide and Conquer

18CS42-Design and Analysis of Feb-May 4

18CS42-Design and Analysis of Feb-May 5

where f(n) is a function that accounts for the time

18CS42-Design and Analysis of Feb-May 8

18CS42-Design and Analysis of Feb-May 11

Analogous results hold for the Ο and Ω notations,

18CS42-Design and Analysis of Feb-May 12

Harivinod 18CS42-Design and Analysis of Feb-May 14

Harivinod 18CS42-Design and Analysis of Feb-May 15

Harivinod 18CS42-Design and Analysis of Feb-May 16

Harivinod 18CS42-Design and Analysis of Feb-May 17

Harivinod 18CS42-Design and Analysis of Feb-May 18

case) T(n) = T(n/2) + c

Harivinod 18CS42-Design and Analysis of Feb-May 22

Harivinod 18CS42-Design and Analysis of Feb-May 23

Harivinod 18CS42-Design and Analysis of Feb-May 25

Harivinod 18CS42-Design and Analysis of Feb-May 27

18CS42-Design and Analysis of

Compared with the straight forward method

Harivinod 18CS42-Design and Analysis of Feb-May 32

Harivinod 18CS42-Design and Analysis of Feb-May 33

Harivinod 18CS42-Design and Analysis of Feb-May 34

Harivinod 18CS42-Design and Analysis of Feb-May 35

Harivinod 18CS42-Design and Analysis of Feb-May 36

Harivinod 18CS42-Design and Analysis of Feb-May 37

Harivinod 18CS42-Design and Analysis of Feb-May 38

• Cmerge(n) - the number of key comparisons performed

Harivinod 18CS42-Design and Analysis of Feb-May 39

• Here a = 2, b = 2, f (n) = n-1 = Θ (n) => d =

Harivinod 18CS42-Design and Analysis of Feb-May 40

Harivinod 18CS42-Design and Analysis of Feb-May 42

• We can divide a list to be sorted in more than

Harivinod 18CS42-Design and Analysis of Feb-May 43

Harivinod 18CS42-Design and Analysis of Feb-May 45

Harivinod 18CS42-Design and Analysis of Feb-May 46

Harivinod 18CS42-Design and Analysis of Feb-May 47

• Select the subarray’s first element: p = A[l].

Harivinod 18CS42-Design and Analysis of Feb-May 48

Harivinod 18CS42-Design and Analysis of Feb-May 49

Harivinod 18CS42-Design and Analysis of Feb-May 50

– As per Master Theorem, Cbest(n) ∈ Θ(n

Harivinod 18CS42-Design and Analysis of Feb-May 52

Harivinod 18CS42-Design and Analysis of Feb-May 53

Harivinod 18CS42-Design and Analysis of Feb-May 54

Harivinod 18CS42-Design and Analysis of Feb-May 55

Harivinod 18CS42-Design and Analysis of Feb-May 56

Harivinod 18CS42-Design and Analysis of Feb-May 57

Harivinod 18CS42-Design and Analysis of Feb-May 58

Harivinod 18CS42-Design and Analysis of Feb-May 60

• How many Multiplications?

Harivinod 18CS42-Design and Analysis of Feb-May 62

Harivinod 18CS42-Design and Analysis of Feb-May 63

Harivinod 18CS42-Design and Analysis of Feb-May 64

Harivinod 18CS42-Design and Analysis of Feb-May 65

Harivinod 18CS42-Design and Analysis of Feb-May 66

Harivinod 18CS42-Design and Analysis of Feb-May 69

Harivinod 18CS42-Design and Analysis of Feb-May 70