Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_5 [2011/03/09 13:43] – [5.1 A First Recurrence: The Mergesort Algorithm] 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 25: / Line 26: @@
   * Look for patterns in runtime at each level
   * Sum up running times over all levels
-Substitute guess solution into recurrence
+Substitute guess solution into recurrence:
 * Check that it works
   * Induction on n
+interesting/readable: 8/8
+====== 5.2 Further Recurrence Relations ======
+summary
+A more general class of algorithms is obtained by considering divideand-
+conquer algorithms that create recursive calls on q subproblems of size
+n/2 each and then combine the results in O(n) time.
+recurrence relation: T(n) < qT(n/2) + cn
+then unroll the recurrence:
+At an arbitrary levelj, we have qJ distinct instances,
+each of size n/2]. Thus the total work performed at level j is qJ(cn/2^j) =
+cn*(q/2)^j.
+More specifically, cn/2^i is the size of the subproblem, and we have for each level q subproblems
+so q^j problems. I think of this as a j-level nested for loops.
+T(n) ≤ Σj=0,logn cn*(q/2)^j
+[cn*(q/2)^logn-cn]/(logn-1) = cn*[(q/2)^logn-1]/(logn-1)
+another handy identity
+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 k for the first part k*n^log2q
+aha.
+Use recurrences to analyze the run time of divide and conquer algorithms
+  *    Number of sub problems
+  *  Size of sub problems
+  *  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