Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2012:journals:carrie:ch5 [2012/03/02 17:04] – created hopkinsc | courses:cs211:winter2012:journals:carrie:ch5 [2012/03/11 22:10] (current) – hopkinsc | ||
|---|---|---|---|
| Line 27: | Line 27: | ||
| * but good if we don't know the exact constants. | * but good if we don't know the exact constants. | ||
| + | ==== 5.2 Further Recurrence Relations ==== | ||
| + | 5.3 T(n) <= qT(n/2) + cn, when n > 2 and t(2) <= c. q is not the number subproblems | ||
| + | |||
| + | What to do with q>2 subproblems | ||
| + | * analyze the first few levels. | ||
| + | * identify a patterns. at abitrary level j we have qq^j distinct instances each of size (n/ | ||
| + | * See diagram on page 216 | ||
| + | * sum over all levels of recursion. | ||
| + | * end up with O(n^(log2(q))) (because of geometric series etc. (5.4) | ||
| + | * can also apply partial substitution - to derive the answer above. (I like unrolling, but see page 217 if need review) | ||
| + | |||
| + | What happens when q = 1 | ||
| + | * well you keep solving half a problem so the work per level is decreasing | ||
| + | * only one instance at each level | ||
| + | * when we sum over we get linear order. (5.5) | ||
| + | |||
| + | Related recurrence | ||
| + | * looking at a recurrence relation of T(n) <= 2T(n/2) + O(n^2) | ||
| + | * same process for Unrolling the recurssion. Can analyze, identify and sum. | ||
| + | |||
| + | ==== 5.3 Counting inversions ==== | ||
| + | The problem | ||
| + | * rankings (netflix suggestions, | ||
| + | * measure ranking by counting the number of inversions between your ranking and comp generated one. | ||
| + | |||
| + | The algorithm | ||
| + | * can find an O(nlogn) solution | ||
| + | * uses a merge and count and sort and count algorithm | ||
| + | * see the algorithm on page 224. did a lot with this in class. makes sense. | ||
| + | |||
| + | ==== 5.4 Finding the closest pair of points ==== | ||
| + | * in class this is where my mind was " | ||
| + | * the problem is how to find the closets points in a set of points | ||
| + | * divide the points into sections and then find min, in each section and around the dividing line. | ||
| + | * first find the mind of your different sections. compare each of those and set delta = to the min of the mins | ||
| + | * THE TRICK is setting up the boxes around the line that are of size delta/2 by delta/2 therefore you only have to check the point and it's seven neighboring boxes. | ||
| + | * really reduces the number of checks | ||
| + | |||
| + | ==== 5.5 interger multiplication==== | ||
| + | The Problem | ||
| + | * want to reduce our running times from o(n^2) to something slightly lower using recursion for example O(n^log2(q)) (saw that before!) | ||
| + | * see algorithm on 233 | ||
| + | * we get O(n^log2(3)) | ||
