Chapter 4

10/2/2023
Divide and conquer Algorithms

1
Divide-and-Conquer
• The most-well known algorithm design strategy:
1. Divide instance of problem into two or more smaller

10/2/2023
instances
2. Solve smaller instances recursively
3. Obtain solution to original (larger) instance by
combining these solutions

2
Divide and conquer
• The divide-and-conquer paradigm involves three steps at
each level of the recursion:

10/2/2023
• Divide the problem into a number of subproblems.
• Conquer the subproblems by solving them recursively. If the
subproblem sizes are small enough, however, just solve the
subproblems in a straightforward manner.
• Combine the solutions to the subproblems into the solution
for the original problem.

3
Divide-and-Conquer Technique (cont.)

a problem of size n

10/2/2023
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 4
Divide-and-Conquer Examples
• Sorting: mergesort and quicksort
• Binary tree traversals
• Multiplication of large integers

10/2/2023
• Matrix multiplication: Strassen’s algorithm
• Closest-pair and convex-hull algorithm
• Binary search: decrease-by-half
(or degenerate divide & conquer)

5
General Divide-and-Conquer
Recurrence
T(n) = aT(n/b) + f (n) where f(n)  (nd), d  0

10/2/2023
Master Theorem: If a < bd, T(n)  (nd)
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 )

6
General Divide-and-Conquer
Recurrence
Solve:
• T(n) = 4T(n/2) + n  T(n)  ?

10/2/2023
• T(n) = 4T(n/2) + n2  T(n)  ?
• T(n) = 4T(n/2) + n3  T(n)  ?

7
Merge sort
• The merge sort algorithm closely follows the
divide-and-conquer paradigm. Intuitively, it

10/2/2023
operates as follows.
• 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
8
to produce the sorted answer.
Merge sort
MERGE(A, p, q, r)
1 𝑛1 ← q - p + 1

10/2/2023
2 𝑛2 ← r - q
3 create arrays L[1 𝑛1 + 1] and R[1 𝑛2 + 1]
4 for i ← 1 to 𝑛1
5 do L[i] ← A[p + i - 1]
6 for j ← 1 to 𝑛2
7 do R[j] ← A[q + j]

9
Merge sort……
8 L[𝑛1 + 1] ← ∞
9 R[𝑛2 + 1] ← ∞

10/2/2023
10 i←1
11 j←1
12 for k ← p to r
13 do if L[i] ≤ R[j]
14 then A[k] ← L[i]
15 i←i+1
16 else A[k] ← R[j]
17 j←j+1
10
combining
• The key operation of the merge sort algorithm is the merging of
two sorted sequences in the "combine" step.

10/2/2023
• To perform the merging, we use an auxiliary procedure
MERGE(A, p, q, r), where A is an array and p, q, and r are indices
numbering elements of the array such that p ≤ q< r.
• The procedure assumes that the subarrays A[p q] and A[q + 1 r]
are in sorted order.
• It merges them to form a single sorted subarray that replaces
the current subarray A[p r].

11
How merge procedure works
• Line 1 computes the length 𝑛1 of thesubarray A[p q], and line
2 computes the length 𝑛2 of the subarray A[q + 1 r].

10/2/2023
• We create arrays L and R ("left" and "right"), of lengths 𝑛1 + 1
and 𝑛2 + 1, respectively, in line 3.
• The for loop of lines 4-5 copies the subarray A[p q] into L[1
𝑛1 ], and the for loop of lines 6-7 copies the subarray A[q + 1
r] into R[1 𝑛2 ].
• Lines 8-9 put the sentinels at the ends of the arrays L and R.
• Lines 10-17, illustrated in Figure below, perform the r - p + 1
basic steps by maintaining the following loop invariant:

12
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

10/2/2023
13
Analysis of Merge sort
• When we have n > 1 elements, we break down the
running time as follows.

10/2/2023
• Divide: The divide step just computes the middle of the
subarray, which takes constant time. Thus, D(n) = Θ(1).
• Conquer: We recursively solve two subproblems, each of
size n/2, which contributes 2T (n/2) to the running time.

14
Analysis …
• Combine: We have already noted that the MERGE
procedure on an n-element subarray takes time Θ(n), so
C(n) = Θ(n).

10/2/2023
• When we add the functions D(n) and C(n) for the merge sort
analysis, we are adding a function that is Θ(n) and a function
that is Θ(1).
• This sum is a linear function of n, that is,Θ(n).
• Adding it to the 2T (n/2) term from the "conquer" step gives
the recurrence for the worst-case running time T (n) of
merge sort:

15
Quicksort
• Select a pivot (partitioning element) – here, the first element
• 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

10/2/2023
remaining n-s positions are larger than or equal to the pivot

A[i]p A[i]p

• Exchange the pivot with the last element in the first (i.e., )
subarray — the pivot is now in its final position
• Sort the two subarrays recursively 16
Hoare’s Partitioning Algorithm

10/2/2023


17
 Quicksort Example

se the preceding algorithm to sort the following:

10/2/2023
5 3 1 9 8 2 4 7

18
Analysis of Quicksort
• Best case: split in the middle — Θ(n log n)
• Worst case: sorted array! — Θ(n2)

10/2/2023
• Average case: random arrays — Θ(n log n)
• Improvements:
• better pivot selection: median of three partitioning
• switch to insertion sort on small subfiles
• elimination of recursion
These combine to 20-25% improvement
• Considered the method of choice for internal sorting of large
files (n ≥ 10000)
19
Binary Search tree
• Def.
• BST is a binary tree in symmetric order

10/2/2023
• A binary tree can either :
• Be empty
• Have a key-value pair and two binary trees
• Symmetric order means that:
• Every node has a key
• Every node’s key is
• larger than all keys in its left subtree
• Smaller than all keys in its right subtree
20
• public class BinarySearch
• {
• public static int binSearch(int a[], int x)
• { // a is sorted int low = 0, high = a.length - 1;
• while (low <= high)

10/2/2023
• { int mid = (low + high) / 2;
• if (x < a[mid]) high = mid - 1;
• else if (x > a[mid]) low = mid + 1;
• else return mid; }
• return Integer.MIN_VALUE; }

• Example1:
• -55 -9 -7 -5 -3 -1 2 3 4 6 9 98 309 21
• Binary search example public static void main(String[] args)
• { int[] a= {-1, -3, -5, -7, -9, 2, 6, 9, 3, 4, 98, 309, -55}; Arrays.sort(a);
// Quicksort for (int i : a)
• System.out.print(" " + i); System.out.println();
System.out.println(“Location of -1 is " + binSearch(a, -1));
System.out.println(“Location of -55 is "+ binSearch(a,-55));

10/2/2023
System.out.println(“Location of 98 is " + binSearch(a, 98));
System.out.println(“Location of -7 is " + binSearch(a, -7));
System.out.println(“Location of 8 is " + binSearch(a, 8)); }
• // Output -55 -9 -7 -5 -3 -1 2 3 4 6 9 98 309
• BinSrch location of -1 is 5
• BinSrch location of -55 is 0
• BinSrch location of 98 is 11
• BinSrch location of -7 is 2
• BinSrch location of 8 is -2147483648
22
Binary search is used to find an element in a sorted array
Divide : Check the middle element
Conquer : Recursively search 1 subarray
Combine : Subproblem solutions
Example2 : Find 15

10/2/2023
3 5 7 8 9 12 15 17 20
3 5 7 8 9 12 15 17 20
3 5 7 8 9 12 15 17 20
3 5 7 8 9 12 15 17 20
3 5 7 8 9 12 15 17 20

23
Binary search performance
• Each iteration cuts search space in half – Analogous to tree
search

10/2/2023
• Maximum number of steps is O(lg n) – There are n/2k values
left to search after each step k
• Successful searches take between 1 and ~lg n steps
• Unsuccessful searches take ~lg n steps every time
• We have to sort the array before searching it – Quicksort
Quicksort takes O(n lg n) steps – This is the bottleneck step
• If we have to sort before each search, this is too slow
• Use binary search tree instead: O(lg n) add, O(lg n) find –
Binary search used on data that doesn’t change (or that
arrives sorted)
• Sort once, search many times 24
• Recurrence for binary search
• T(n)=1T(n/2)+Θ(1)
• 1-represent the subproblems
• n/2-represent subproblem size
• Θ(1)-represent the work of dividing and combining

10/2/2023
25