Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:chen:chapter_5 [2011/03/09 14:29] – [5.3 Counting Inversions] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_5 [2011/03/14 04:13] (current) – zhongc
@@ Line 1: / Line 1: @@
+====== Overview ======
 definition:P234
 Divide and conquer refers to a class of algorithmic techniques in which one
@@ Line 120: / Line 121: @@
 interesting/readable: 7/7
-====== 5.4 Finding the losest Pair of Points ======
+====== 5.4 Finding the closest Pair of Points ======
+Closest pair. Given n points in the plane, find a pair with smallest Euclidean distance
+between them.
+Brute force N^2
+simplified case:
+if all points are on one line, then we only need to compare in one dimension.
+so sort the pioints in either dimension: nlogn
+iterate through it and find the closest pair: n
+total nlogn
+D/C:
+Divide: draw vertical line L so that roughly ½n points on each side
+Combine: find closest pair with one point in each side
+better combine:
+Find closest pair with one point in each side, assuming that distance < δ
+where δ = min(left_min_dist, right_min_dist)
+we only need to consider points within the strip enclosed by δ.
+Sort remaining points by y-coordinate. Scan points in y-order and compare distance between each point and next 7 neighbors. If any of these
+distances is less than δ, update δ.
+O(nlog2n) logn levels and every level is nlogn if we sort every time
+could go down to nlogn if we sort only once and return the sorted lists each time.
+interesting/readbale: 7/7
+====== 5.5 Integer multiplication ======
+summary:
+Problem: the multiplication of two integers
+If we use brute force, it is an N2 algorithm.
+We want to do better than that. Additions and subtractions are cheaper, substituting those for multiplications and divisions can
+sometimes help the complexity. We do this by doing divide and conquer.
+Attempt 1 :
+represent the x and y in binary form, multiplication produces 4 instances
+way branching T(n)= 4T(n/2) + cn does not help. ended up with O(N2)
+if we could get q down tp 3, we have some savings.
+Matrix multiplications:
+Divide and conquer in MM: devide into submatrices and combine the results
+decimal wars:
+Best known. O(n2.376) [Coppersmith-Winograd, 1987]
+ But really large constant
+• Conjecture. O(n2+ε) for any ε > 0.
+• Caveat. Theoretical improvements to
+Strassen are progressively less practical.
+Interesting/reabale: 9/9