Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_5 [2011/03/09 14:43] – [5.4 Finding the closest Pair of Points] 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 141: / Line 142: @@
 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