Algorithms & Data Structures (Winter 2022) Algorithm Paradigms – Divide and Conquer 2
Announcements
Copyright By PowCoder代写 加微信 powcoder
• Complete Search
• Divide and Conquer.
• Introduction. • Examples.
• Dynamic Programming. • Greedy.
Divide and Conquer – Arithmetic Operations
• Given 2 (binary) numbers, we want efficient algorithms to:
• Add 2 numbers
• Multiply 2 numbers (using divide-and-conquer!)
Divide and Conquer – Arithmetic Operations
Integer addition
Addition. Given two n-bit integers a and b, compute a + b. Subtraction. Given two n-bit integers a and b, compute a – b.
Grade-school algorithm. Θ(n) bit operations.
Remark. Grade-school addition and subtraction algorithms are asymptotically optimal.
Divide and Conquer – Arithmetic Operations
Integer multiplication
Multiplication. Given two n-bit integers a and b, compute a × b. Grade-school algorithm. Θ(n2) bit operations.
Conjecture. [Kolmogorov 1952] Grade-school algorithm is optimal. Theorem. [Karatsuba 1960] Conjecture is wrong.
Divide and Conquer – Arithmetic Operations
Divide and Conquer – Arithmetic Operations
Divide-and-conquer multiplication
T・o multiply two n-bit integers x and y:
・Divide x and y into low- and high-order bits. ・Multiply four 1⁄2n-bit integers, recursively.
Add and shift to obtain result.
a = ! x / 2m” b = x mod 2m c = ! y / 2m” d = y mod 2m
use bit shifting to compute 4 terms
(2m a + b) (2m c + d) = 22m ac + 2m (bc + ad) + bd 1234
Ex. x =10001101 y =11100001 ab cd
Divide and Conquer – Arithmetic Operations
Divide and Conquer – Karatsuba trick
Avengers Assemble In Final Battle Scene – AVENGERS: ENDGAME (2019). Taken from youtube
Divide and Conquer – Karatsuba trick
Divide and Conquer – Karatsuba trick
Divide and Conquer – Integer Multiplication
Divide and Conquer – Closest points
• Given n points in the plane, find the pair that is closest together.
• Applications in:
• Computational Geometry.
• Graphics, computer vision, geographic information systems, molecular modeling. 14
Divide and Conquer – Closest points
• Given n points in the plane, find the pair that is closest together.
Divide and Conquer – Closest points
• 1-D Solution.
• We first sort the points (merge sort) => O(n log n).
• We’d walk through the sorted list, computing the distance from each point to the one that comes after it => O(n).
• One of these distances must be the minimum one. • 2-D Solution.
• we could try sorting the points by their y-coordinate (or x-coordinate) and hoping that the two closest points were near one another in the order of this sorted list.
• it is easy to construct examples in which they are very far apart
• Find the closest pair among the points in the “left half”
• Find the closest pair among the points in the “right half” • Be careful with the distances that have not been considered.
• One point is the left and one point in the right half.
Divide and Conquer – Closest points
• 2-D Solution.
Divide and Conquer – Closest points
• Partition X into two sets:
• XL has the n/2 smallest x values (‘left’) • XR has the n/2 largest x values (‘right’)
Divide and Conquer – Closest points
t(n/2) t(n/2)
Divide and Conquer – Closest points
• XL and XR each have n/2 points. Thus there are n/2 * n/2 pairs of points such that one is in XL and the other in XR.
• Finding the pair with minimum distance using “brute force” would take O(n2), which is too slow.
• Can we solve this problem in time O(n), instead on O(n2)?
Divide and Conquer – Closest points
• Let the closest pair in XL have distance dL. • Let the closest pair in XR have distance dR.
Divide and Conquer – Closest points
•ObservethattofindtheclosestpairwithonepointinXL and the other point in XR, we only need to consider points that are a distance . from the line that separates L and R.
The observation does not necessarily reduce the number of points we Need to consider
Divide and Conquer – Closest points
• Consider the subset of the plane consisting of all points within distance of . We can partition this subset into boxes (squares with horizontal and vertical sides of length ). One row of this subset will consist of four boxes whose horizontal sides have the same y-coordinates.
Divide and Conquer – Closest points
• Consider a point p that lies between the two green lines.
• Is there another point between the green lines that has a y value greater
than that of p and is at a distance less than
It is sufficient to check those points whose y values are between py and py +
Q: How many points do we need to check in the worst case?
Divide and Conquer – Closest points
• Q: How many points do we need to check in the worst case? • A: At most 7.
• Remember that square cells of width can contain at most 1 point. • Remember that we also sorted the points by their y coordinate
Divide and Conquer – Closest points
• Q: How many points do we need to check in the worst case? • A: At most 7.
Divide and Conquer – Closest points
t(n/2) t(n/2)
Divide and Conquer – Closest points
t(n/2) t(n/2)
Same than merge sort
c4n O(nlogn)
Matrix multiplication – If time allows
Matrix multiplication – divide and conquer
Matrix multiplication – divide and conquer
Matrix multiplication – Strassen’s trick
Matrix multiplication – Strassen’s trick
Matrix multiplication – Strassen’s trick
Matrix multiplication – Strassen’s trick
Matrix multiplication
• Complete Search
• Divide and Conquer.
• Introduction. • Examples.
• Dynamic Programming. • Greedy.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com