Algorithm Design Techniques: Divide and Conquer

 
Lecture 2: Divide and Conquer
 
Basic Algorithm Design Techniques
 
Divide and conquer
Dynamic Programming
Greedy
 
Common Theme: To solve a large, complicated
problem, break it into many smaller sub-problems.
Divide and Conquer
 
Idea: Break the problem into several 
unrelated
 sub-
problems, then 
combine
 the solutions to solve the
original problem.
 
Recipe:
1. 
(divide)
 Divide the problem into sub-problems
2. 
(conquer) 
Solve the sub-problems recursively.
3. 
(merge)
 Combine the solutions.
Example 1 Merge Sort
 
Goal: Sort an array of numbers in ascending order.
Input: Array a[] = {6, 2, 4, 1, 5, 3, 7, 8}
 
Algorithm:
 
MergeSort(a[])
1.
IF
 Length(a) < 2 
THEN
 
RETURN 
a.                          (Base Case)
2.
Partition a[] evenly into two arrays b[], c[].         (Divide)
3.
b[] = MergeSort(b[])
4.
c[] = MergeSort(c[])                                                   (Conquer)
5.
RETURN
 Merge(b[], c[]).                                           (Merge)
Merge Sort: Example:
{6, 2, 4, 1, 5, 3, 7, 8}
{1, 2, 3, 4, 5, 6, 7, 8}
{6, 2, 4, 1}
{1, 2, 4, 6}
{5, 3, 7, 8}
{3, 5, 7, 8}
{6, 2}
{2, 6}
{4, 1}
{1, 4}
{5, 3}
{3, 5}
{7, 8}
{7, 8}
Key Design Step: How to Merge
 
{1, 2, 4, 6}   {3, 5, 7, 8}
Idea: Smallest element must be between the first
elements of the two arrays.
Determine the smallest, remove it and continue.
 
Merge(b[], c[])
1.
a[] = empty
2.
i = 1, j = 1
3.
WHILE
 i <= Length(b[]) 
OR
 j <= Length(c[])
4.
     
IF
 b[i] < c[j] 
THEN
5.
           a.append(b[i]); i = i+1
6.
     
ELSE
7.
           a.append(c[j]); j = j+1
8.
RETURN
 a[]
Careful when you
actually write a
program (i,j can
be out of bound)
Example 2 Counting Inversions
 
Goal: Given array a[], count the number of pairs (i,j)
such that i < j but a[i] > a[j].
 
Input: Array a[] = {6, 2, 4, 1, 5, 3, 7, 8}
Answer = 9
Designing the algorithm
 
Recall Recipe:
 
 
Recipe:
1. 
(divide)
 Divide the problem into sub-problems
2. 
(conquer) 
Solve the sub-problems recursively.
3. 
(merge)
 Combine the solutions.
Failed Attempt:
 
Partition a[] evenly to two arrays b[], c[].
Count Inversions recursively.
Combine results
a[] = {6, 2, 4, 1, 5, 3, 7, 8}, 9 inversions
b[] = {6, 2, 4, 1}, 5 inversions
c[] = {5, 3, 7, 8}, 1 inversion
#inversion = #inversion in b + #inversion in c
                         + 
#inversion between b[], c[]
 
 
Can take O(n
2
) time!
How to count inversions more efficiently?
 
b[] = {6, 2, 4, 1}, 5 inversions
c[] = {5, 3, 7, 8}, 1 inversion
For each number in b, want to know 
how many
numbers in c are smaller.
6: 2, 2: 0, 4: 1, 1: 0, result = 2+0+1+0 = 3.
Much easier if c[] is sorted!
 
Idea: Can sort the arrays when we are counting
inversions.
Sort&Count
 
Sort&Count(a[])
1.
IF
 Length(a) < 2 
THEN
 
RETURN (
a[], 0).                          (Base Case)
2.
Partition a[] evenly into two arrays b[], c[].                    (Divide)
3.
(b[], count_b) = Sort&Count(b[])
4.
(c[], count_c) = Sort&Count(c[])                                        (Conquer)
5.
(a[], count_bc) = Merge&Count(b[], c[]).                         (Merge)
6.
RETURN
 a[], count_b+count_c+count_bc.
 
Merge&Count
 
b[]  =  {1, 2, 4, 6}                  c[] = {3, 5, 7, 8}
 
 
                           {1, 2, 3, 4, 5, 6, 7, 8}
When 4 goes into the array, pointer in c[] is
pointing at 5 (2
nd
 element), so 4 is larger than 1
element in c[].
When 6 goes into the array, pointer in c[] is
pointing at 7 (3
rd
 element), so 6 is larger than 2
elements in c[].
Merge&Count
 
Merge&Count(b[], c[])
1.
a[] = empty
2.
i = 1, j = 1
3.
count = 0
4.
WHILE
 i <= Length(b[]) 
OR
 j <= Length(c[])
5.
     
IF
 b[i] < c[j] 
THEN
6.
           a.append(b[i]); i = i+1
7.
         
  count = count + (j - 1)
8.
     
ELSE
9.
           a.append(c[j]); j = j+1
10.
RETURN
 a[], count
The i-th element of a[]
is smaller than c[j], but
larger than c[
1,2,…, j-1
]
Slide Note
Embed
Share

Algorithm design techniques such as divide and conquer, dynamic programming, and greedy algorithms are essential for solving complex problems by breaking them down into smaller sub-problems and combining their solutions. Divide and conquer involves breaking a problem into unrelated sub-problems, solving them recursively, and then merging the solutions. The approach is illustrated through examples like Merge Sort and Counting Inversions, demonstrating the process of dividing, conquering, and merging to efficiently solve problems.


Uploaded on Sep 11, 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.

E N D

Presentation Transcript


  1. Lecture 2: Divide and Conquer

  2. Basic Algorithm Design Techniques Divide and conquer Dynamic Programming Greedy Common Theme: To solve a large, complicated problem, break it into many smaller sub-problems.

  3. Divide and Conquer Idea: Break the problem into several unrelated sub- problems, then combine the solutions to solve the original problem. Recipe: 1. (divide) Divide the problem into sub-problems 2. (conquer) Solve the sub-problems recursively. 3. (merge) Combine the solutions.

  4. Example 1 Merge Sort Goal: Sort an array of numbers in ascending order. Input: Array a[] = {6, 2, 4, 1, 5, 3, 7, 8} Algorithm: MergeSort(a[]) 1. IF Length(a) < 2 THEN RETURN a. (Base Case) 2. Partition a[] evenly into two arrays b[], c[]. (Divide) 3. b[] = MergeSort(b[]) 4. c[] = MergeSort(c[]) (Conquer) 5. RETURN Merge(b[], c[]). (Merge)

  5. Merge Sort: Example: {6, 2, 4, 1, 5, 3, 7, 8} {1, 2, 3, 4, 5, 6, 7, 8} {5, 3, 7, 8} {3, 5, 7, 8} {6, 2, 4, 1} {1, 2, 4, 6} {7, 8} {7, 8} {5, 3} {3, 5} {6, 2} {2, 6} {4, 1} {1, 4}

  6. Key Design Step: How to Merge {1, 2, 4, 6} {3, 5, 7, 8} Idea: Smallest element must be between the first elements of the two arrays. Determine the smallest, remove it and continue. Merge(b[], c[]) 1. a[] = empty 2. i = 1, j = 1 3. WHILE i <= Length(b[]) OR j <= Length(c[]) 4. IF b[i] < c[j] THEN 5. a.append(b[i]); i = i+1 6. ELSE 7. a.append(c[j]); j = j+1 8. RETURN a[] Careful when you actually write a program (i,j can be out of bound)

  7. Example 2 Counting Inversions Goal: Given array a[], count the number of pairs (i,j) such that i < j but a[i] > a[j]. Input: Array a[] = {6, 2, 4, 1, 5, 3, 7, 8} Answer = 9

  8. Designing the algorithm Recall Recipe: Recipe: 1. (divide) Divide the problem into sub-problems 2. (conquer) Solve the sub-problems recursively. 3. (merge) Combine the solutions.

  9. Failed Attempt: Partition a[] evenly to two arrays b[], c[]. Count Inversions recursively. Combine results a[] = {6, 2, 4, 1, 5, 3, 7, 8}, 9 inversions b[] = {6, 2, 4, 1}, 5 inversions c[] = {5, 3, 7, 8}, 1 inversion #inversion = #inversion in b + #inversion in c + #inversion between b[], c[] Can take O(n2) time!

  10. How to count inversions more efficiently? b[] = {6, 2, 4, 1}, 5 inversions c[] = {5, 3, 7, 8}, 1 inversion For each number in b, want to know how many numbers in c are smaller. 6: 2, 2: 0, 4: 1, 1: 0, result = 2+0+1+0 = 3. Much easier if c[] is sorted! Idea: Can sort the arrays when we are counting inversions.

  11. Sort&Count Sort&Count(a[]) 1. IF Length(a) < 2 THEN RETURN (a[], 0). (Base Case) 2. Partition a[] evenly into two arrays b[], c[]. (Divide) 3. (b[], count_b) = Sort&Count(b[]) 4. (c[], count_c) = Sort&Count(c[]) (Conquer) 5. (a[], count_bc) = Merge&Count(b[], c[]). (Merge) 6. RETURN a[], count_b+count_c+count_bc.

  12. Merge&Count b[] = {1, 2, 4, 6} c[] = {3, 5, 7, 8} {1, 2, 3, 4, 5, 6, 7, 8} When 4 goes into the array, pointer in c[] is pointing at 5 (2nd element), so 4 is larger than 1 element in c[]. When 6 goes into the array, pointer in c[] is pointing at 7 (3rd element), so 6 is larger than 2 elements in c[].

  13. Merge&Count Merge&Count(b[], c[]) 1. a[] = empty 2. i = 1, j = 1 3. count = 0 4. WHILE i <= Length(b[]) OR j <= Length(c[]) 5. IF b[i] < c[j] THEN 6. a.append(b[i]); i = i+1 7. count = count + (j - 1) 8. ELSE 9. a.append(c[j]); j = j+1 10. RETURN a[], count The i-th element of a[] is smaller than c[j], but larger than c[1,2, , j-1]

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#