CS代考 Algorithms & Data Structures (Winter 2022) Algorithm Paradigms

Algorithms & Data Structures (Winter 2022) Algorithm Paradigms – Divide and Conquer

Announcements
Comp 251(c) 2022

• 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 ¬ ë(p+r)/2û
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 The work nd of the root dominates
• 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

Case2(r<1):a1):a>bd
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

Related Posts