www.Vidyarthiplus.
com
CS2251-Design and Analysis of Algorithms year/sem:II/IV
unit-2
Divide-and-Conquer
The most-
most-well known algorithm design strategy:
1. Divide instance of problem into two or more smaller
instances
2. Solve smaller instances recursively
3. Obtain solution to original (larger) instance by combining
these solutions
.
Design and Analysis of Algorithms Unit III
Divide-and-Conquer Technique (cont.)
a problem of size n
subproblem 1 subproblem 2
of size n/2 of size n/2
a solution to a solution to
subproblem 1 subproblem 2
a solution to
the original problem
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
1
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Divide-and-Conquer Examples
I Sorting: mergesort and quicksort
I Binary tree traversals
I Binary search (?)
I Multiplication of large integers
I Matrix multiplication: Strassen’
Strassen’s algorithm
I Closest-
Closest-pair and convex-
convex-hull algorithms
.
Design and Analysis of Algorithms Unit III
General Divide-and-Conquer Recurrence
T(n) = aT( n/b) + f (n) where f(n) ∈ Θ(nd), d ≥ 0
aT(n/b)
Theorem: If a < bd, T(n) ∈ Θ(nd)
Master Theorem:
If a = bd, T(n) ∈ Θ(nd log n)
If a > bd, T(n) ∈ Θ(nlog b a )
Note: The same results hold with O instead of Θ.
4T(n/2) + n ⇒ T(n) ∈ ?
Examples: T(n) = 4T
4T(n/2) + n2 ⇒ T(n) ∈ ?
T(n) = 4T
4T(n/2) + n3 ⇒ T(n) ∈ ?
T(n) = 4T
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
2
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Mergesort
I Split array A[0..n
A[0..n-1] in two about equal halves and make
copies of each half in arrays B and C
I Sort arrays B and C recursively
I Merge sorted arrays B and C into array A as follows:
• Repeat the following until no elements remain in one of
the arrays:
– compare the first elements in the remaining
unprocessed portions of the arrays
– copy the smaller of the two into A, while
incrementing the index indicating the unprocessed
portion of that array
• Once all elements in one of the arrays are processed,
copy the remaining unprocessed elements from the other
array into A.
.
Design and Analysis of Algorithms Unit III
Pseudocode of Mergesort
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
3
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Pseudocode of Merge
.
Design and Analysis of Algorithms Unit III
Mergesort Example
8 3 2 9 7 1 5 4
8 3 2 9 7 1 5 4
8 3 2 9 71 5 4
8 3 2 9 7 1 5 4
3 8 2 9 1 7 4 5
2 3 8 9 1 4 5 7
1 2 3 4 5 7 8 9
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
4
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Analysis of Mergesort
I All cases have same efficiency: Θ(n log n)
I Number of comparisons in the worst case is close to
theoretical minimum for comparison-
comparison-based sorting:
⎡log2 n!⎤ ≈ n log2 n - 1.44n
1.44n
I Space requirement: Θ(n) (not
(not in-
in-place)
I Can be implemented without recursion (bottom-
(bottom-up)
.
Design and Analysis of Algorithms Unit III
Quicksort
I Select a pivot (partitioning element) – here, the first element
I Rearrange the list so that all the elements in the first s
positions are smaller than or equal to the pivot and all the
elements in the remaining n-s positions are larger than or
equal to the pivot (see next slide for an algorithm)
A[i]≤p A[i]≥p
I Exchange the pivot with the last element in the first (i.e., ≤)
subarray — the pivot is now in its final position
I Sort the two subarrays recursively
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
5
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Partitioning Algorithm
.
Design and Analysis of Algorithms Unit III
Quicksort Example
5 3 1 9 8 2 4 7
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
6
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Analysis of Quicksort
I Best case: split in the middle — Θ(n log n)
I Worst case: sorted array! — Θ(n2)
I Average case: random arrays — Θ(n log n)
I Improvements:
• better pivot selection: median of three partitioning
• switch to insertion sort on small subfiles
• elimination of recursion
These combine to 20-
20-25% improvement
I Considered the method of choice for internal sorting of large
files (n
(n ≥ 10000)
.
Design and Analysis of Algorithms Unit III
Binary Search
Very efficient algorithm for searching in sorted array:
array:
K
vs
A[0] . . . A[m
A[m] . . . A[n
A[n-1]
If K = A[m
A[m], stop (successful search); otherwise, continue
searching by the same method in A[0..m
A[0..m-1] if K < A[m
A[m]
and in A[m
A[m+1..n
+1..n-1] if K > A[m
A[m]
l ← 0; r ← n-1
while l ≤ r do
m ← ⎣( )/2⎦
⎣(l+r)/2⎦
if K = A[m
A[m] return m
A[m] r ← m-1
else if K < A[m
else l ← m+1
return -1
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
7
www.Vidyarthiplus.com
Design and Analysis of Algorithms Unit 3
Analysis of Binary Search
I Time efficiency
worst-case recurrence: Cw (n) = 1 + Cw( ⎣n/2⎦
• worst- /2⎦ ), Cw (1) = 1
solution: Cw(n) = ⎡log2(n+1)⎤
+1)⎤
This is VERY fast: e.g., Cw(106) = 20
I Optimal for searching a sorted array
I Limitations: must be a sorted array (not linked list)
I Bad (degenerate) example of divide-
divide-and-
and-conquer
I Has a continuous counterpart called bisection method for
solving equations in one unknown f(x) = 0 (see Sec. 12.4)
.
Design and Analysis of Algorithms Unit III
Binary Tree Algorithms
Binary tree is a divide-
divide-and-
and-conquer ready structure!
Ex. 1: Classic traversals (preorder, inorder, postorder)
Algorithm Inorder(
Inorder(T)
if T ≠ ∅ a a
Inorder(Tleft)
Inorder( b c b c
print(root of T) d e d e
Inorder(Tright)
Inorder(
Efficiency: Θ(n)
.
Design and Analysis of Algorithms Unit III
www.Vidyarthiplus.com
8
