Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Design and Analysis of algorithms
Description: Divide and Conquer Algorithm
Description: Divide and Conquer Algorithm
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Chapter – 2 – Divide and Conquer
Algorithm
Introduction
Recurrence relations
Multiplying large Integers Problem
Binary Search
Merge Sort
Quick Sort
Matrix Multiplication
Exponentiation
By: Madhuri V
...
DIVIDE: A problem’s instance is divided into several smaller
instances of the same problem, ideally of about the same size
...
RECUR: Solve the sub-problem recursively
...
CONQUER: If necessary, the solutions obtained for the
smaller instances are combined to get a solution to the
original instance
...
Vaghasia(Assistant Professor)
2
Introduction
•Diagram shows the general divide & conquer plan
Problem
of Size
n
Problem
of Size
n/2
Problem
of Size
n/2
Solution to sub
problem 1
Solution to
sub problem
2
Solution to
original
problem
By: Madhuri V
...
Vaghasia(Assistant Professor)
4
• The computing time of above procedure of divide and conquer is
given by the recurrence relation
• T(n)=
,if n is small
g(n)
T(n1)+T(n2)+…+T(nr)+f(n) ,if n is
sufficiently large
By: Madhuri V
...
• These are held together and coordinated by the algorithm's core recursive
structure
...
Vaghasia(Assistant Professor)
6
Recurrence relations
• Divide-and-conquer algorithms often follow a generic pattern: they tackle a
problem of size n by recursively solving, say, a sub problems of size n/b and
then combining these answers in O(n⋀d) time, for some a; b; d > 0 (in the
multiplication algorithm, a = 3, b = 2, and d = 1)
...
• We next derive a closed-form solution to this general recurrence so that we
no longer have to solve it explicitly in each new instance
...
Vaghasia(Assistant Professor)
7
Recurrence relations
By: Madhuri V
...
Vaghasia(Assistant Professor)
9
Multiplying large Integers Problem
• Consider that we want to perform operation 1234*981
...
(12 and 34)
• 1234 = 10⋀2 * 12 + 34 = 1234
• For 0981 * 1234 consider following things
...
Vaghasia(Assistant Professor)
10
Multiplying large Integers Problem
• The above procedure still needs four half-size multiplications; wy, wz, xy and
xz
...
• Is it possible to obtain wz + xy at the cost of single multiplication? Our
equeation is like
• Result = (w + x) * (y + z) = wy + (wz + xy) + xz
By: Madhuri V
...
Vaghasia(Assistant Professor)
12
Multiplying large Integers Problem
• If each of the three half – size multiplications is carried out by the classic
algorithm, the time needed to multiply two n – figure numbers is f(n)
...
So the total time required is,
• T(n)=f(n)+c
...
Vaghasia(Assistant Professor)
13
Multiplying large Integers Problem
• Calculate multiplication of following number using divide and conquer
• 1234*4321 = ?
By: Madhuri V
...
Vaghasia(Assistant Professor)
15
Multiplying large Integers Problem
• At each successive level of recursion the sub problems get halved in size
...
• Therefore, the height of the tree is log 2 n
...
Each problem recursively produces three smaller
ones
...
By: Madhuri V
...
Therefore the total time spent at
depth k in the tree is
By: Madhuri V
...
Vaghasia(Assistant Professor)
18
Multiplying large Integers Problem
By: Madhuri V
...
Vaghasia(Assistant Professor)
20
Binary Search
Function binrec(T[i…j], x)
{
if(j
else
{
k 🡨 (i + j) /2
if(x==t[k]) then
return k
else if(x <= t[k]) then
return binrec(T[i
...
Vaghasia(Assistant Professor)
21
Complexity of Binary Search Method
•When n= 64 BinarySearch is called to reduce size to n=32 When
n= 32 BinarySearch is called to reduce size to n=16 When n= 16
BinarySearch is called to reduce size to n=8 When n= 8
BinarySearch is called to reduce size to n=4 When n= 4
BinarySearch is called to reduce size to n=2 When n= 2
BinarySearch is called to reduce size to n=1
•Let us consider a more general case where n is a power of 2
...
•2k = n Taking log of both sides
k = log n
• Recurrence for binary search is T(n)=T(n/2)+1 (the time to search in an
array of 1 element is constant)
We conclude from there that the time complexity of the Binary
search method is O(log n)
...
Vaghasia(Assistant Professor)
22
Merge Sort
•The problem of sorting a list of numbers lends itself
immediately to a divide-and-conquer strategy: split the list into
two halves, recursively sort each half, and then merge the two
sorted sub lists
...
Vaghasia(Assistant Professor)
23
Merge Sort
• The correctness of this algorithm is self-evident, as long as a correct merge
subroutine is specified
...
The
rest of z[
...
By: Madhuri V
...
Vaghasia(Assistant Professor)
25
Merge Sort
• MERGE (A, p, q, r )
n1 ← q − p + 1
n2 ← r − q
Create arrays L[1
...
n2 + 1]
for i ← 1 to n1 then
do L[i] ← A[p + i − 1]
for j ← 1 to n2 then
do R[j] ← A[q + j ]
L[n1 + 1] ← ∞
R[n2 + 1] ← ∞
i←1
j←1
FOR k ← p TO r
DO IF L[i ] ≤ R[ j]
THEN A[k] ← L[i]
i←i+1
ELSE A[k] ← R[j]
j←j+1
By: Madhuri V
...
• For merge linear amount of work is done, so time taken is g(n)=O(n)
...
Vaghasia(Assistant Professor)
27
Quick Sort
• Given an array of n elements (e
...
, integers):
• If array only contains one element, return array
Else
pick one element to use as pivot
...
Vaghasia(Assistant Professor)
28
Quick Sort
40
20
10
80
60
50
7
By: Madhuri V
...
Vaghasia(Assistant Professor)
30
Quick Sort
• Procedure partition(A,p,r)
{
x<-A[r]
i<-p-1
for j<-p to r-1
{
if A[j]<=x
then i<-i+1
exchange A[i]<->A[j]
}
exchange A[i+1]<->A[r]
return i+1
}
By: Madhuri V
...
•Best case running time: O(n log n)
•Worst case running time? O(n∧2)
•Recursion:
•Partition splits array in two sub-arrays:
•one sub-array of size 0
•the other sub-array of size n-1
•Quicksort each sub-array
•Depth of recursion tree? O(n)
•Number of accesses per partition? O(n)
By: Madhuri V
...
•Best case running time: O(n log n)
•T(n)<=2T(n/2)+∅(n)
•Worst case running time? O(n∧2)
•T(n)=T(n-1)+T(0)+∅(n)=T(n-1)+∅(n)
•Recursion:
•Partition splits array in two sub-arrays:
•one sub-array of size 0
•the other sub-array of size n-1
•Quicksort each sub-array
•Number of accesses per partition? ∅(n)
By: Madhuri V
...
Vaghasia(Assistant Professor)
34
Iterative Matrix Multiplication
Input: matrices A and B
Let C be a new matrix of the appropriate size
For i from 1 to n:
For j from 1 to p:
Let sum = 0
For k from 1 to m:
Set sum ← sum + Aik × Bkj
Set Cij ← sum
Return C
By: Madhuri V
...
, A22, B22 % by computing m = n/2
X1 ← MMult(A11, B11, n/2)
X2 ← MMult(A12, B21, n/2)
X3 ← MMult(A11, B12, n/2)
X4 ← MMult(A12, B22, n/2)
X5 ← MMult(A21, B11, n/2)
X6 ← MMult(A22, B21, n/2)
X7 ← MMult(A21, B12, n/2)
X8 ← MMult(A22, B22, n/2)
C 11 ← X1 + X2
C 12 ← X3 + X4
C 21 ← X5 + X6
C 22 ← X7 + X8
Output C
End If
By: Madhuri V
...
• For quite a while, this was widely believed to be the best running time
possible, and it was even proved that in certain models of computation no
algorithm could do better
...
By: Madhuri V
...
Vaghasia(Assistant Professor)
38
Optimized Matrix Multiplication Algorithm
Strassen(A, B)
If n = 1
A=[1 2
34]
B=[1 2
34]
Output A × B
Else
Compute A11, B11,
...
Vaghasia(Assistant Professor)
39
Matrix Multiplication
By: Madhuri V
...
We wish to compute the
exponentiation x = a^n
...
•If n is small, the obvious algorithm is adequate
...
Vaghasia(Assistant Professor)
41
Exponentiation
•a ∧ n = return a
if n = 1
return (a ∧ n/2) ∧ 2
return a * a ∧ n-1
if n is even
otherwise
a ∧ 29 = a * a ∧ 28 = a(a ∧ 14) ∧ 2 ……
...
By: Madhuri V
...
Vaghasia(Assistant Professor)
43
Any Question ?
Please don’t carry it
By: Madhuri V
Title: Design and Analysis of algorithms
Description: Divide and Conquer Algorithm
Description: Divide and Conquer Algorithm