Algorithms Design and Analysis with Divide and Conquer Approach

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.

• Algorithms
• Divide and Conquer
• Recursive Algorithms
• Optimization
• Complexity

candido_a Follow

Uploaded on Sep 26, 2024 | 1 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. 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

2. Main Ingredients Input Size Iterative Algorithms Writing Summations Recursive Algorithms Writing Recurrence Divide and Conquer Technique Writing Recurrence

3. 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?

4. 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

5. 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)

6. 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.

7. 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

8. 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.

9. 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.

10. (x0+x1)(y0+y1)=x1y1+(x1y0+y1x0)+x0y0 Thus, x1y0+y1x0 = (x0+x1)(y0+y1) - x0y0- x1y1 Thus, only 3 multiplications suffice

11. 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

12. Multiplying Two polynomials of degree n Exactly same idea as that of large integers. Treat the polynomial as an integer consisting of n digits.

13. Searching Iterative : Sequential Search Divide and Conquer (Iterative/Recursive)

14. Sorting Insertion Sort Selection Sort Bubble Sort Merge Sort Quick Sort

15. Recursive vs Iterative Algorithms n! Fibonacci Numbers Finding Maximum/Sum