ANALYSIS AND DESIGN

OF ALGORITHMS
(UNIT3)
OUTLINE
> Introduction
> Recurrence and different methods to solve
> Multiplying large Integers Problem
> Problem Solving using divide and conquer algorithm
Binary Search,
Max-Min problem,

> Sorting (Merge Sort, Quick Sort)

> Matrix Multiplication, Exponential
 > Introduction
• The big problem is broken down into smaller sub problems and solution to
these sub problems is obtained.
• Binary search, Merge sort, Quick sort, Matrix multiplication are used divide
and conquer strategy.

General method:
1) Divided into smaller sub problems
2) These sub problems are solved independently
3) Combining all the solutions of sub problems into solution of the whole.

> Multiplying Large Integers Problems

Grade-school multiplication (positional numeral system) not convenient for performing multiplication of large
integers.
Example :

• Apply this method on integers 2101 and 1130. c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)
• C = a * b = 2101 * 1130 = (21+01) * (11+30) – (231+30)
• Divide the numbers in equal = (22*41) – 261
a1 = 21, a0 = 01 = 641
b1 = 11, b0 = 30 a * b = c2 10 4 + c1 10 2 + c0
= 231 * 10 4 + 641 * 10 2 + 30
• Let us obtain c0,c1, and c2 = 2374130
c2 = a1 * b1 = 21 * 11 = 231
c0 = a0 * b0 = 01 * 30 = 30

Divide and conquer technique

• Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or
more times to deal with closely related sub problems.
• These algorithms typically follow a divide-and-conquer approach:
• The divide-and-conquer approach involves three steps at each level of the recursion:
• Divide: Break the problem into several sub problems that are similar to the original problem but smaller in size,
• Conquer: Solve the sub problems recursively, and If the sub problem sizes are small enough, just solve the sub
problems in a straightforward manner.
• Combine: Combine these solutions to create a solution to the original problem.
Methods to Solve Recurrence

1) Substitution
Class Task : Search about
2) Homogeneous (characteristic equation)
substitution method and
3) Inhomogeneous
tree method
4) Master method
5) Recurrence tree
6) Intelligent guess work
7) Change of variable
8) Range transformations

Master Method : Time complexity of recurrence method using master method

(Substitution method solve all types of time complexity problem but this method are slow /
master method solve specific types of problem here it is… )
T(n) = aT (n/b) + f(n)
a >= 1, b > 1
Example : T(n) = T(n-1) + 1 Example : T(n) = 8T(n/2) + n2
= 1T (n-1) / 1 + 1 = aT (n/b) / n2
= aT (n-1) / b + 1 a = 8, b = 2 Condition true so
a = 1, b = 1 a >= 1, b > 1 we using master
a >= 1, b > 1
This example not 8 >= 1, 2 > 1 method
solve with this
1 >= 1, 1 > 1 method a
T(n) = nlogb [u(n)] h(n) = f(n)
[u(n)] values depend on h(n) n logba
 > Problem solving using Divide and Conquer
The problems that can be solved using divide and conquer strategy are:
1) Binary Search
2) Max - Min Problem
3) Merge Sort
4) Quick Sort
5) Matrix Multiplication
6) Exponential
1) Binary Search
• It is an efficient searching method.
• While searching the elements using this method the most essential
thing is that the elements in the array should be sorted.
• An element which is to be searched is called KEY element.
• A[m] be the mid element of array A.
• Three conditions are tested while searching:
1. If KEY = A[m] then desired element is present in the list.
2. Otherwise if KEY < A[m] then search the left sub list.
3. Otherwise if KEY > A[m] then search the right sub list.
 Ex: 32 12 13 05 03 26 11 09 19 13 19 26 32 13
0 1 2 3 4 5 6 7 8 5 6 7 8 5
Key = 13 Low m High Low
High m = key
Sorted 03 05 09 11 12 13 19 26 32 m = low + high - 1 / 2 m = low + high / 2 13 = 13
element
m= 5+8-1/2 =6 m = 5 + 5 / 2 = 5 Key element found in index 5
0 1 2 3 4 5 6 7 8
m > key
Low m High
19 > 13
m < key Then check left sub list
m = low + high / 2 12 < 13
Left side low + high +1 When low + high
m = 0 + 8 / 2 = 4 Then check right sub list addition is odd
Right side low + high - 1
Key = 09 m = low + high + 1 / 2
m= 0+3+1/2 =2
Class Task : 11 26 13 05 08 20
m > key m = key
12 > 09 Find out Key 26 and Key 3
09 = 09
Then check left sub list Key element found in index 2
03 05 09 11 05 10 15 20 25 30 35 40 45
0 1 2 3
Low High Find out Key 10 and Key 35

Ex : 32 12 13 05 03 11
0 1 2 3 4 5
m
Key = 12 2) Max - Min Problem
m = low + high / 2
m= 0+5-1/2 =2
m > key
13 > 12
Then check left sub list

32 12 m = low + high + 1 / 2
m= 0+1+1/2 =1
0 1 m = key
12 = 12
Key element found in index 1
3) Merge Sort
• Merge sort is one of the most popular sorting algorithm that is based on the principle of Divide and
Conquer Algorithm.
• There are three steps:
Divide: Partition array into two sub lists with n/2 elements each.
Conquer: Sort the sub lists.
Combine: Merge the sub lists into a unique sorted group.
Algorithm:
Step 1 : Begin
Step 2 : Divide all the items of array in two item Ex : 7, 1, 8, 3, 9, 2, 10, 12
pairs, if single item remain make it single group 7, 1, 8, 3, 9, 2, 10, 12
Step 3 : Sort each of the pair
Step 4 : Merge two pairs into a single pair 1, 7, 3, 8, 2, 9, 10, 12
Step 5 : Sort the merge pair 1, 3, 7, 8, 2, 9, 10, 12
Step 6 : Repeat the above steps until the all
elements of array are not sorted 1, 2, 3, 7, 8, 9, 10, 12
Step 7 : Exit
 4) Quick Sort
Quick sort algo. Items separates the list of elements into two parts and sort each part recursively. It used
divide and conquer method. In this method the partition of list performed based on pivot element. The list
is divide into two partition such that all elements to the left pivot are smaller and all elements to the right
of pivot are greater.
Algorithm: Ex : 50 03 01 60 65 45 90 13 67

Step 1 : Begin Pivot element

Step 2 : Select the start element of array as a Right side smallest element is 13 so we replace with pivot element
“pivot” element
13 03 01 60 65 45 90 50 67
Step 3 : Scan and find the smallest element from
right side of array Pivot element
Step 4 : Exchange both element Left side greatest element compare to pivot is 60 so we replace 60
Step 5 : Scan and find biggest element from left with pivot element
side of list and exchange both element 13 03 01 50 65 45 90 60 67
Step 6 : Repeat the process until the all elements
Pivot element
of left side are smaller and right side elements are
greater than pivot element Right side smallest element is 45 so we replace with pivot element
Step 7 : Now two sub list are available, apply same 13 03 01 45 65 50 90 60 67
process until all elements of array are not sorted
Step 8 : Exit Pivot element
Left side greatest element is 65 so we replace with pivot element
13 03 01 45 50 65 90 60 67

Pivot element
 (now, in this array right side is no smaller element compare to pivot element and left side no greater element
compare to pivot element)
13 03 01 45 50 65 90 60 67

(Small) Pivot element (Greater)

13 03 01 45 65 90 60 67

Pivot element Pivot element

01 03 13 45 60 90 65 67

(Small) (Greater) Pivot element

Pivot element
Sorted array 60 65 90 67

(Small) (Greater)
Pivot element
Sorted array

90 67

Pivot element
Output : 67 90
01 03 13 45 50 60 65 67 90
> Matrix Multiplication
Thus to accomplish 2* 2 matrix multiplication there are
total 8 multiplications and 4 additions.

Strassen showed that 2 * 2 matrix multiplication can be accomplished

in 7 multiplication and 18 additions or subtractions.
• The divide and conquer approach can be used for implementing
Strassen’s matrix multiplication.
Divide: Divide matrices into sub-matrices: A0, A1, A2,..
Conquer: Use a group of matrix multiply equations.
Combine: Recursively multiply sub-matrices and get the final result of
multiplication after performing required additions or subtractions.
> Exponential
THANK
YOU
Prof. Pandya Khushi