Algorithms & Data Structures (Winter 2022) Algorithm Paradigms – Divide and Conquer
Announcements
Comp 251(c) 2022
Copyright By PowCoder代写 加微信 powcoder
• Complete Search
• Divide and Conquer.
• Introduction. • Examples.
• Dynamic Programming. • Greedy.
Algorithmic Paradigms – Divide and Conquer
• It is a problem solving paradigm where we try to make a problem simpler by ‘dividing’ it into smaller parts and ‘conquering’ them.
• Recursive in structure
• Divide the problem into sub-problems that are similar to the original but
smaller in size
• Usually by half or nearly half.
• Conquer the sub-problems by solving them recursively. If they are small enough, just solve them in a straightforward manner.
• Combine the solutions to create a solution to the original problem 4
Decrease and Conquer
• Sometimes we’re not actually dividing the problem into many subproblems, but only into one smaller subproblem
• Usually called decrease and conquer
• The most common example of this is binary search O(log n).
• Given a sorted array of elements.
1. Base case: the array is empty, return false
2. Compare x to the element in the middle of the array
3. If it’s equal, then we found x and we return true
4. If it’s less, then x must be in the left half of the array 4.1 Binary search the element (recursively) in the left half
5. If it’s greater, then x must be in the right half of the array 5.1 Binary search the element (recursively) in the right half
Decrease and Conquer
Divide and Conquer – Merge Sort
Sorting Problem: Sort a sequence of n elements into non- decreasing order.
• Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each
• Conquer: Sort the two subsequences recursively using merge sort.
• Combine: Merge the two sorted subsequences to produce the sorted answer.
Divide and Conquer – Merge Sort
Conquer – trivial cases
Combine – Sub-problems
Divide and Conquer – Merge Sort
Original Sequence
Sorted Sequence
MergeSort(A, p, r)
INPUT: a sequence of n numbers stored in array A OUTPUT: an ordered sequence of n numbers
MergeSort (A, p, r) // sort A[p..r] by divide & conquer
then q ¬ ë(p+r)/2û
MergeSort (A, p, q)
MergeSort (A, q+1, r)
Merge (A, p, q, r) // merges A[p..q] with A[q+1..r]
Initial Call: MergeSort(A, 1, n)
Comp 251(c) 2022
Merge(A, p, q, r)
Merge(A, p, q, r)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
n1¬q–p+1 n2¬r–q fori¬1ton1
do L[i] ¬ A[p + i – 1] forj¬1ton2
do R[j] ¬ A[q + j] L[n1+1] ¬ ¥ R[n2+1] ¬ ¥
j¬1 fork¬ptor
do if L[i] £ R[j] then A[k] ¬ L[i]
i¬i+1 else A[k] ¬ R[j]
Input: Array containing sorted subarrays A[p..q] and A[q+1..r].
Output: Merged sorted subarray in A[p..r].
Sentinels, to avoid having to check if either subarray is fully copied at each step.
Comp 251(c) 2022
Merge – Example
iiiii jjjjj
Comp 251(c) 2022
Merge – Correctness
Merge(A, p, q, r)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
n1¬q–p+1 n2¬r–q fori¬1ton1
do L[i] ¬ A[p + i – 1] forj¬1ton2
do R[j] ¬ A[q + j] L[n1+1] ¬ ¥ R[n2+1] ¬ ¥
j¬1 fork¬ptor
do if L[i] £ R[j] then A[k] ¬ L[i]
i¬i+1 else A[k] ¬ R[j]
Loop Invariant property (main for loop)
• At the start of each iteration of the for
loop, subarray A[p..k – 1] contains the k – p smallest elements of L and R in sorted order.
• L[i] and R[j] are the smallest elements of L and R that have not been copied back into A.
Initialization:
Before the first iteration:
•A[p..k – 1] is empty, k = p => k – p = 0. •i = j = 1.
•L[1] and R[1] are the smallest
elements of L and R not copied to A. 13
Comp 251(c) 2022
Merge – Correctness
Merge(A, p, q, r)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
n1 ¬q–p+1 n2¬r–q fori¬1ton1
do L[i] ¬ A[p + i – 1] forj¬1ton2
do R[j] ¬ A[q + j] L[n1+1] ¬ ¥ R[n2+1] ¬ ¥
j¬1 fork¬ptor
do if L[i] £ R[j] then A[k] ¬ L[i]
i¬i+1 else A[k] ¬ R[j]
Maintenance:
Case 1: L[i] £ R[j]
•By LI, A contains k – p smallest elements of L and R in sorted order.
•By LI, L[i] and R[j] are the smallest elements of L and R not yet copied into A.
•Line 13 results in A containing k – p + 1 smallest elements (again in sorted order). Incrementing i and k reestablishes the LI for the next iteration.
Case 2: Similar arguments with L[i] > R[j]
Termination:
•On termination, k = r + 1. By LI, A[p..k-1], which is A[p..r], contains k-p=r–p+1 smallest elements of L and R in sorted order. •LandRtogethercontainn1 +n2 +2=r–p+3
elements including the two sentinels. All but the two largest (i.e., sentinels) have been copied in A.
Comp 251(c) 2022
MergeSort – Analysis
• Running time T(n) of Merge Sort:
• falls out from the three steps of the basic paradigm
• Divide: computing the middle takes O(1)
• Conquer: solving 2 subproblems takes 2T(n/2) • Combine: merging n elements takes O(n)
T(n) = O(1) if n = 1 T(n) = 2T(n/2) + O(n) + O(1) if n > 1
Þ T(n) = O(n lg n)
Comp 251(c) 2021
In general – Analysis – Recurrence
Trivial case of size <= constant
# of subproblems
size of subproblems
divide time combine time
Comp 251(c) 2021
Solving recurrences
• Substitution method: we guess a bound and then use mathematical induction to prove that our guess is correct.
• Recursion-tree method: converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.
• Master method: provides bounds for recurrences of the form.
MergeSort – Substitution method
log! 2𝑛 = log! 2+log! 𝑛 log!2𝑛 −1=log!𝑛
Comp 251(c) 2022
MergeSort – Recursion Tree
assuming n is a power of 2
Comp 251(c) 2022
Recursion Tree
Notice that a, b and d are independent of n
Note that nd represents
the work done outside
the recursive call
Comp 251(c) 2022
Recursion Tree
height of call tree
number of leaves.
Recursion stops at the base case, typically when problem size is a small number
Comp 251(c) 2022
Recursion Tree – Good VS Evil
Comp 251(c) 2022
Let’s the battle begin
Taken from pinterest
Comp 251(c) 2022
Let’s the battle begin (supplemental)
• But first lets define (recall) the allowed ‘super powers’. • Geometric series power (convergence power).
• Sum of a number of terms that have a constant ratio between successive terms.
• In general:
!+!+!+!+ ! +........ ! " # $ !%
𝑆! = ( 𝑟" = 1 + 𝑟 + 𝑟% + ⋯ + 𝑟! "#$
• Multiplying both sides by r gives.
r𝑆! = 𝑟 + 𝑟% + 𝑟& + ⋯ + 𝑟!'(
Comp 251(c) 2022
Let’s the battle begin (supplemental)
• Geometric series (convergence power). • Substracting the two previous equations.
(1 − 𝑟)𝑆!= (1 + 𝑟 + 𝑟% + ⋯ + 𝑟!) − (𝑟 + 𝑟% + 𝑟& + ⋯ + 𝑟!'() (1 − 𝑟)𝑆!= 1 − 𝑟!'(
! 1 −𝑟!'( 𝑆!=(𝑟"= 1−𝑟
• For-1
• Ifa=bd(thereisatie)
• The amount of work is the same at every recursion level i. • All levels have the same ‘worst’ case.
• Might expect O(nd log n) => nd for all the log levels
• If a > bd (evil wins)
• The amount of work is increasing with the recursion level i. • Worst case is in the leaves (i.e., i = logbn)
• Might expect => O(nlog(a)) => O(#leaves) because leaves dominates 32
Comp 251(c) 2022
Good VS Bad – battle possible results
If a = bd (there is a tie) If a < bd (good wins)
If a > bd (evil wins)
Comp 251(c) 2022
Case1(r=1):a=bd
Comp 251(c) 2022
Case1(r=1):a=bd
Comp 251(c) 2022
Case2(r<1):a
Comp 251(c) 2022
Case3(r>1):a>bd
See Supplemental Slide
Comp 251(c) 2022
Case3(r>1):a>bd
, 2020 Comp 251(c) 2022 39
Master Method (summary)
Comp 251(c) 2022
Master Method (summary)
– Limitations:
• Defined for worst case.
• Sub-problems need to
have the same size.
• Applicable to recursions
of divide-and-conquer
Comp 251(c) 2022
Master theorem
• Goal: Recipe for solving common recurrences.
a = # subproblems
b = factor by which the subproblem size decreases
f(n) = work to divide/merge subproblems
Comp 251(c) 2022
Master theorem – Case 1
The formula works with 𝜀 = log! 3 − 1 > 0 𝑓 𝑛 =𝑛=𝑂 𝑛”#$!%& “#$!%&’
Comp 251(c) 2022
Master theorem – Case 2
𝑓 𝑛 =Θ 𝑛log𝑛 =Θ(𝑛”#$!!log𝑛)
Comp 251(c) 2022
Master theorem – Case 3
1st property satisfied with 𝜀 = 4 − log( 3 𝑓 𝑛 = 𝑛) = Ω(𝑛”#$” %*((&”#$” %))
2nd property satisfied with c=%(
3F 𝑛 )≤𝑐F𝑛) 4
Comp 251(c) 2022
Master theorem – Applications
𝑘=log!1=0;𝑓 𝑛 =2- 2- =Ω 𝑛.*”#$!
1F2-! ≤1F2- 2
T(n)=3*T(n/2)+n2 ⇒T(n)=Θ(n2) (case3)
T(n) = T(n/2) + 2n
⇒ T(n) = Θ(2n) (case 3)
T(n) = 16 * T(n/4) + n
⇒ T(n) = Θ(n2) (case 1)
T(n) = 2 * T(n/2) + n log n ⇒T(n)=nlog2n (case2)
T(n) = 2n * T(n/2) + nn
⇒ Does not apply!!
𝑘=log!3;𝑓 𝑛 =𝑛! 𝑛! =Ω 𝑛”#$!%*(!&”#$!%)
3F 𝑛 ! ≤3F𝑛! 2 4
𝑘=log(16=2;𝑓 𝑛 =𝑛 𝑛 = 𝑂 𝑛!&’
𝑘=log!2=1;𝑓 𝑛 =𝑛log𝑛
𝑛log𝑛 = Θ 𝑛’𝑙𝑜𝑔’𝑛
Comp 251(c) 2022
Master theorem – Other variants – Akra-Bazzi
Comp 251(c) 2022
• Complete Search
• Divide and Conquer.
• Introduction. • Examples.
• Dynamic Programming. • Greedy.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com