Algorithms Design and Analysis with Divide and Conquer Approach
Design and Analysis of
Algorithms with Emphasis on
Divide and Conquer
Neelima Gupta
Department of Computer Science
University of Delhi
ngupta@cs.du.ac.in
people.du.ac.in/~ngupta
Main Ingredients
•
Input Size
•
Iterative Algorithms
–
Writing Summations
•
Recursive Algorithms
–
Writing Recurrence
•
Divide and Conquer Technique
–
Writing Recurrence
Problems to discuss
•
Compute 3
n
for large n
–
What is the input size?
•
Compute Sqrt(n) (assume n is a perfect square)
–
What is the input size?
•
Product of two large integers : x and y each consisting of n digits
–
What do you understand by “large”?
–
What is the input size?
•
Product of two polynomials each of degree n with small coefficients
–
What do you understand by “small”?
–
What is the input size?
•
Searching
–
What is the input size?
•
Sorting
–
What is the input size?
Computing 3
n
•
(Simplification: Assume n to be a power of 2)
•
3
n
= 3.
3
n-1
–
Iterative
–
Time : T(n) = sum_{i = 1 to n} 1 = O(n)–
Recursive
–
Time: T(n) = T(n-1) + 1 which leads to above
series on expansion
•
Divide and Conquer (Recursion)
3
n
=
3
n/2 .
3
n/2
•
Time: T(n) = T(n/2) + 1 = O(log n)
•
Divide and Conquer (Iterative)
3
n
=
3
n/2 .
3
n/2
Bottom up
Compute Sqrt(n) )
(assume n is a perfect square)
•
Iterative
•
Time : T(n) = sum_{i = 1 to n} 1 = O(n)•
Divide and Conquer (Iterative/Recursive)
•
Time: T(n) = T(n/2) + 1 = O(log n)
Multiplying 2 large integers each
of n digits
Iterative: O(n
2
) time by the usual successive
add algorithm.
We can reduce this time using divide and
conquer strategy.
Multiplying 2 large integers
Suppose the 2 numbers are
2345 and 3854
Split the numbers into roughly 2 halves
Here x
0
=45; x
1
=23; y
0
=54; y
1
=38;
x = x
1
.10
n/2
+ x
0
(1)
y = y
1
.10
n/2
+ y
0
(2)
xy=x
1
y
1
.10
n
+(x
1
y
0
+y
1
x
0
).10
n/2
+x
0
y
0
(3)
x = 23*10
2
+ 45
y = 38*10
2
+ 54
x
1
y
1
=874;x
1
y
0
=1242;x
0
y
1
=1710;x
0
y
0
=2430;
Using (1),(2),(3) answer came out to be
= 874*10
4
+(2952)*10
2
+2430
adding these numbers take linear time.
Time Analysis
•
Computing
x
1
y
1
,(x
1
y
0
+y
1
x
0
),x
0
y
0
T(n)=4T(n/2)+cn
=
Ө
(n
2
)
So, no improvement. We’ll use a smarter way to compute the
middle term.
(x
0
+x
1
)(y
0
+y
1
)=x
1
y
1
+(x
1
y
0
+y
1
x
0
)+x
0
y
0
Thus,
x
1
y
0
+y
1
x
0
= (x
0
+x
1
)(y
0
+y
1
) - x
0
y
0
- x
1
y
1
Thus, only 3 multiplications suffice
•
So T(n)is reduced to
T(n)=3T(n/2)+cn
=
Ө
(n
log
2
3
)<
Ө
(n
2
)
where 3T(n/2) is the time required to multiply
x
1
y
1
, (x
0
+x
1
)(y
0
+y
1
), x
0
y
0
Multiplying Two polynomials of
degree n
•
Exactly same idea as that of large integers.
•
Treat the polynomial as an integer
consisting of n digits.
Searching
•
Iterative : Sequential Search
•
Divide and Conquer (Iterative/Recursive)
Sorting
•
Insertion Sort
•
Selection Sort
•
Bubble Sort
•
Merge Sort
•
Quick Sort
Recursive vs Iterative Algorithms
•
n!
•
Fibonacci Numbers
•
Finding Maximum/Sum
Explore the intricacies of algorithm design and analysis, with a focus on divide and conquer techniques. Delve into topics such as iterative and recursive algorithms, writing summations, divide and conquer strategy, and more. Discover how to compute large numbers, polynomials, perform searching and sorting efficiently. Uncover the power of divide and conquer in simplifying computations and optimizing time complexity.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Design and Analysis of Algorithms with Emphasis on Divide and Conquer Neelima Gupta Department of Computer Science University of Delhi ngupta@cs.du.ac.in people.du.ac.in/~ngupta
Main Ingredients Input Size Iterative Algorithms Writing Summations Recursive Algorithms Writing Recurrence Divide and Conquer Technique Writing Recurrence
Problems to discuss Compute 3n for large n What is the input size? Compute Sqrt(n) (assume n is a perfect square) What is the input size? Product of two large integers : x and y each consisting of n digits What do you understand by large ? What is the input size? Product of two polynomials each of degree n with small coefficients What do you understand by small ? What is the input size? Searching What is the input size? Sorting What is the input size?
Computing 3n (Simplification: Assume n to be a power of 2) 3n = 3.3n-1 Iterative Time : T(n) = sum_{i = 1 to n} 1 = O(n) Recursive Time: T(n) = T(n-1) + 1 which leads to above series on expansion Divide and Conquer (Recursion) 3n =3n/2 .3n/2 Time: T(n) = T(n/2) + 1 = O(log n) Divide and Conquer (Iterative) 3n =3n/2 .3n/2 Bottom up
Compute Sqrt(n) ) (assume n is a perfect square) Iterative Time : T(n) = sum_{i = 1 to n} 1 = O(n) Divide and Conquer (Iterative/Recursive) Time: T(n) = T(n/2) + 1 = O(log n)
Multiplying 2 large integers each of n digits Iterative: O(n2) time by the usual successive add algorithm. We can reduce this time using divide and conquer strategy.
Multiplying 2 large integers Suppose the 2 numbers are 2345 and 3854 Split the numbers into roughly 2 halves Here x0=45; x1=23; y0=54; y1=38; x = x1.10n/2 + x0 (1) y = y1.10n/2 + y0(2) xy=x1y1.10n+(x1y0+y1x0).10n/2+x0y0 (3) x = 23*102 + 45 y = 38*102 + 54
x1y1=874;x1y0=1242;x0y1=1710;x0y0=2430; Using (1),(2),(3) answer came out to be = 874*104+(2952)*102+2430 adding these numbers take linear time.
Time Analysis Computing x1y1,(x1y0+y1x0),x0y0 T(n)=4T(n/2)+cn = (n2) So, no improvement. We ll use a smarter way to compute the middle term.
(x0+x1)(y0+y1)=x1y1+(x1y0+y1x0)+x0y0 Thus, x1y0+y1x0 = (x0+x1)(y0+y1) - x0y0- x1y1 Thus, only 3 multiplications suffice
So T(n)is reduced to T(n)=3T(n/2)+cn = (nlog23)< (n2) where 3T(n/2) is the time required to multiply x1y1 , (x0+x1)(y0+y1), x0y0
Multiplying Two polynomials of degree n Exactly same idea as that of large integers. Treat the polynomial as an integer consisting of n digits.
Searching Iterative : Sequential Search Divide and Conquer (Iterative/Recursive)
Sorting Insertion Sort Selection Sort Bubble Sort Merge Sort Quick Sort
Recursive vs Iterative Algorithms n! Fibonacci Numbers Finding Maximum/Sum
