Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter5 [2011/03/09 04:27] – created shangw
+++ courses:cs211:winter2011:journals:wendy:chapter5 [2011/03/14 00:52] (current) – shangw
@@ Line 20: / Line 20: @@
 The "guessing" way becomes more interesting in this case. Because the connecting time cn cannot cancel with anything here. Therefore, we slightly adjust the guess from kn^d to kn^d-ln so that the ln will do the cancellation.
 If we have a very special case, q=1, it is not hard to show that the running time is bounded by O(n).
+A related problem is to change the recurrence relationship a little:
+T(n)<=2T(n/2)+O(n^2), from unrolling the recurrence we obtain that the bound of the running time os O(n^2). I wonder what application does this relationship has.
+Readability is 7, the modification of guessing part is fun to read.
+===== Section 3: Counting Inversions =====
+This section talks about a concrete example using divide and conquer--counting inversion.
+The problem is to count how many inversions are there in a sequence of n numbers. The brute-force way is to check each pair which has a bad running time O(n^2). We want to use the divide and conquer method to improve the running time.
+What we do the merge-sort + count-sort algorithm. Basically, we look at two already sorted list and see how many inversions there are if combine them together-which can be counted in linear time when using a counter, then sort the combined list to add together with the other combined sorted list.
+The running time is then O(log(n)n) since the recurrence relationship is the T(n)<=2T(n/2)+cn one.
+I think this way of counting inversion is smart.
+Readability is 7.
+===== Section 4: Finding the Closest Pair of Points =====
+Here is another application of the divide conquer algorithm.
+The general idea is to divide the plane into two parts, find out the minimum distance of each part, compare both with the distances between points beside the boundary of the two planes and hence get a minimum distanced pair of the combined plane. The most difficult part to implement is the combining part. First it is not hard to conceive that let x be the smaller distance from the two planes to be combined, if the new minimum distance comes from between points from the two planes, then the points have to locate from the strip centered at the splitting vertical line with wideth 2x. Sort the points inside the strip according to their y coordinate in ascending order. Another smart observation is if si, sj are two points in the strip and |i-j|>=15 (or 12, or 7, the key is it to be a constant), then they must be apart more than x--I think it is very clever. This enables us to for each point only scan the 7 neighborhood above instead the entire collection of points in the strip, which only takes linear time instead of quadratic time. Hence the recursive relation is:
+T(n)<=2T(n/2)+O(nlogn) (for sorting the points in the strip). =O(logn^2n)
+Readability is 8.
+===== Section 5: Integer Multiplication =====
+This section introduces another problem that uses the divide conquer algorithm--integer multiplication.
+This seemingly straight forward problem actually takes O(n^2) if using brute-force algorithm. But we can improve the running time using divide and conquer method.
+The first try is to divide the original problem into 4 subproblems:
+xy=x1y1+(x1y0)2^n/2+(x0y1)2^n/2+x0y0.
+However, the recurrence relationship T(n)<=4T(n/2)+cn is still only bounded by O(n^2). But notice that if we only use 3 subproblems instead of 4, the running time can be reduced. We need to look at the problem slightly differently:
+xy=x1y1+(x1y1+x0y0+x1y0+x0y1-x1y1+x0y0)2^n/2+x0y0.
+=x1y1+(p-x1y1-x0y0)2^n/2+x0y0
+where p=(x0+x1)(y0+y1).
+Now the recurrence relationship is T(n)<=3T(n/2)+cn<=O(n^1.59)
+Readability is 7.