Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_5 [2011/03/09 14:16] – [5.2 Further Recurrence Relations] 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 58: / Line 59: @@
 for any a > 1 and b > 1, we have a^logb = b^loga
-therefore, we have (cn/logn-1)*[n^log(q/2)-1] which is some constant c for the first part k*n^log2q
+therefore, we have (cn/logn-1)*[n^log(q/2)-1] which is some constant k for the first part k*n^log2q
 aha.
@@ Line 67: / Line 68: @@
   *  Number of times divided (number of levels)
   *  Cost of merging problems
+interesting/readable: 9/9
+====== 5.3 Counting Inversions ======
+summary:
+The Problem
+Movie site tries to match your movie
+preferences with others
+ You rank n movies
+ Movie site consults database to find people with similar tastes
+**ollaborative filtering**
+We need a way to Comparing Rankings:
+need a similarity metric: how to measure how similar two peopl's preferences are?
+specifically, count the **number of inversions between two rankings**
+kind of reminds of the earth movers distance in the research, which is the amount of work to shift a histogram into another.\
+Brute Force Solution
+Look at every pair (i,j) and determine if they are an inversion
+obviously runs in N^2
+D/C algo:
+• Divide: separate list into two pieces
+• Conquer: recursively count inversions in each half
+• Combine: count inversions where ai and aj are in different halves, and return sum of three quantities
+Combine: count blue-green inversions
+ Assume each half is sorted
+ Count inversions where ai and aj are in different halves
+ Merge two sorted halves into sorted whole
+Recurrence Relation:
+T(n) ≤ T(n/2) + T(n/2) + O(n)
+T(n) --> nlogn
+implementation:
+Sort-and-Count(L)
+if list L has one element
+return 0 and the list L
+Divide the list into two halves A and B
+(iA, A) = Sort-and-Count(A)
+(iB, B) = Sort-and-Count(B)
+(i, L) = Merge-and-Count(A, B)
+return i = iA + iB + i and the sorted list L
+interesting/readable: 7/7
+====== 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