Let's take:
1) Another look at finding closed forms from recurrences
2) And an overview of two Master theorem examples.
I should have really thought about the intuition behind unwinding recurrences. My goal at the moment is to be able to understand recurrence unwinding such that I will tackle such a question without erasing (i.e. right the first time). Let's say that we have an algorithm that takes T(n) time, with n being the input "length". I thought that finding a closed form was about unwinding until an arbitrary n, but that didn't really have a purpose with regards to finding a closed form. If we know that n is an integer power of, say 3, then there exists a positive integer k such that n = 2^k (It is important that k is positive because we want to unwind when T(n) has a recursive definition for n, and this occurs in recursive definitions when n is greater than a certain breakpoint which is greater than 1). Then, we should unwind until that k, so that we can "cancel" things out, since n can be in terms of k.
Notice that n = 2^k is equivalent to k = log(base 2)n. Also notice that when unwinding, we find a closed form that is in terms of log(base 2)n. I figure that we choose k such that it is what our T(n) should be bounded by - and if we have the right k - then a closed form should be found (i.e, we won't have an infinite recurrence and be unable to "cancel" (#0) things out). We should also choose k such that things that get in the way such as floors and ceilings can be simplified.
Finally, we can prove that T(n) is equivalent to its closed form by a form of induction (usually complete, since we need to assume that the recursive components of T(n) hold to show that T(n) itself holds).
On the other hand, I notice that there are "simpler" recurrences to unwind, such as the Assignment 2's OMCOFS recurrence. Here, we didn't need to guess a k in terms of n that our recurrence was bounded by. We simply unwounded until n. I guess one difference was that we were seeking a resemblance to the fibonacci sequence, so we could simply unwind until that. But if we had the simplified time complexity of binary search that ran at T(n) = 1 + T(n/2) time for n > 1, we would still need to find a k in terms of n to bound the recurrence by in order to reach a closed form. I guess that we need such a k if we had a T(n) that can't "cancel" itself out after n substitutions (unwindings). I realize that we may need to do a bit of unwinding before we discover that necessary k in terms of n.
Another interesting thing to note: T(n) won't be able to "cancel" itself out if indices are chosen unwisely. By indices, I mean that we plug (apply the recurrence) and chug (simplify the result) (MIT Mathematics for Computer Science 788). This can happen if I obtain something like T(n - (n + 1)) = T(-1), which is undefined for recurrences (even T(0) can sometimes be undefined). Usually, I see this happen when T(n) is applied to itself several times in one unwinding (like our Assignment 2's question 1 H(n) recurrence, or tutorial 3's question 3 G(n) recurrence).
Now onto Master Theorem examples. In class, we covered two, namely: n-bit multiplication and finding closest points pairs.
For n-bit multiplication, I finally understood why Gauss's trick saved another subproblem from being evaluated. First thing to keep in mind is that we have a recursive call when we do a multiplication. Second, we should think like computers in that we should think step by step. Since our focus here is on the multiplication algorithm time complexity, when we see an expression like (a + b)(c + d), do not conjure up the idea that the computer simplifies this through FOIL (first, outside, inside, last) into the form (a*c + a*d + b*c + b*d). Then obviously this would seem to take equivalent time to brute force multiplication (#-1). If we ignore this innate intuition of simplifying the expression and instead see the bigger picture (#-2), we notice that the expression itself requires only one multiplication, the asterisk in: (a + b) * (c + d). Then we know that Gauss's trick saves one recursive call. For more information, see the first part of http://www.cs.berkeley.edu/~jordan/courses/170-fall05/notes/dc.pdf, on multiplication.
For finding closest points pairs, I know that we need (perhaps not exactly "why we need"):
- to recursively find the minimum distance on each side of the closest points.
- to find the points that might have a close distance across the "separating line".
But for the most part I'm dumbfounded on how sorting is applied to the problem. I have read some material online, but I can only hope to go to office hours by now. My conjecture is that the problem with explaining the closest point pairs problem is a lack of focus on definitions and failing to accommodate to readers' intuitions (as in #1).
I'll be posting about recursive recurrences next.
#0: By "cancel", for the most part, I mean having a recurrence reach a base case:
T(n) = T(n - 1)
= T(n - 2)
.
.
.
= T(n - n) = T(0) = 1 (assuming that T(n) has a defined "base case" like this.)
#-1: (Psychology?) Note. My explanation to you will require me to "break the fourth wall". I don't know the exact terms, but I see many textbooks try to explain the process of how the reader thinks as he /she approaches the problem. I think all that is necessary is for the book to admit to the reader that the it is trying to explain what the reader thinks and should not think, i.e. warn of the reader's pretense in answering a question.
#-2: This is what most textbooks, and many professors seem to say, but it's this that leads to a failure in communication and understanding. Terms like "think about it", "see the bigger picture", and "think outside the box" implies some avant-garde, clear, and simple way to think about things, but it really can make the learners feel like low-lifes. Explanations should be as explicit as possible, with relevant, pure material as backup.
----------------------------------------------------------------------------------------------------------------------------------
I'm creating this section below to record milestones through the course. I figured that this would be unnecessary, as my progress is implied by the topics I've posted on, but I'll take the time to make explicit how I feel so far with the course (But in all honesty, I am reluctant to take away from my immersion from the course material. Writing this section forces me to break this "wall" explicitly).
Induction:
- Simple: Solidified.
- Complete: Solidified.
- Well-Ordering: Solidified, but I there is one extra reading material I wish to look at.
- Structural: Solidified, but I am disappointed with the level of rigor the course had for the topic.
- Pitfalls: Solidified, but I hope to find more.
- Quizzes: Solidified. The TA should not have told us mathematical induction was the only one allowed.
- Test: Solidified.
Recurrences and recursion:
- Solidified, with me having learned this post's lesson on the test.
- Quizzes: Solidified. Looking forward to more examples.
- Test: Solidified, with me having learned this post's lesson on the test. The TA should not have withhold the geometric series from us and we should not have been suggested to self-study program recursive correctness.
Program correctness:
- Recursive: Solidified, self studied but I hope to read on a proof of this for merge sort.
- Iterative: I have yet to take a look at.
No comments:
Post a Comment