February 07, 2005
Divide and Conquer Problems
A few questions related to divide an conquer algorithms. These are not required or graded, but might be useful for studying for exams. These questions deal with divide and conquer algorithms.
1. How does divide and conquer improve the efficiency of searching in binary search?
solution
Kind of an easy question, maybe too easy. Basically, you narrow your search space by 1/2 an each iteration.
2. Suppose you have a divide and conquer algorithm for multiplying large matrices. Suppose your algorithm divides each of the original n by n matrices into n/3 by n/3 matrices. Suppose that you have a way of multiplying and recombining the n/3 matrices into the n by n product that requires 8 matrix multiplications and 5 matrix additions. What is the complexity of your new algorithm (use Equation 7.1)? Does your algorithm perform better than Strassen's algorithm?
solution
This is an impossible situation, but we will do the analysis anyway.
T(n) = 8(T(n/3)) + O(n^2)
So that l = 8, b = 3, k = 2 and 8 < 9 so you get big-Theta(n^k) = big-Theta(n^2).
3. Prove that m1 + m2 + m4 - m7 really is the correct value for the bottom left corner of the product matrix on page 242 on the book. The product matrix is in equation 7.10 and the multiplicands appear earlier on teh same page.
solution
sort of a tedious but easy little proof. basically, you expand each m-term and simplify the resulting expression and find that you get a21b11 + a22b21 as desired.
Posted by jones at 02:44 PM | Comments (0)
January 21, 2005
Prim's algorithm on a disconnected graph
What happens if Prim's algorithm is deployed on a disconnected graph? A disconnected graph has some nodes that are not connected to any other nodes.
Posted by jones at 02:33 PM | Comments (1)
January 14, 2005
max rule, big O, NP
I think the general feeling in the class is that some homework would be helpful to let people know what they should be learning at this point in the class. Here's a few questions you should be able to answer. Its due Wednesday January 19 (before class, via email as usual). Well, I am not sure where I was getting that feeling from, but that's not what I got discussing that idea with the class. So we've created "study problems." Study problems are like homework problems except they aren't required or graded. I will post solutions later.
1. Prove that O(f(n) + g(n) + h(n)) = O(max(f(n),g(n),h(n)). You don't need to give the level of detail we gave in class last week, but you do need to write the proof. I would expect to see proofs that are about 3-6 lines long.
solution Proof idea: the proof follows the proof in the book except the constant is 3 instead of 2.
Proof: suppose q(x) is in O(f(x) + g(x) + h(x)) then q(x) is in O(max(f(x), g(x), h(x)) because three times the greatest of f(x), g(x) and h(x) is greater than or equal to the sum, more precisely:
q(x) <= c(f(x) + g(x) + h(x)) <= 3c(max(f(x), g(x), h(x)).
Next, suppose q(x) is in O(max(f(x), g(x), h(x)) then q(x) is in O(f(x) + g(x) + h(x)) because the greatest of f(x),g(x) and h(x) is less than or equal the sum of all three (assuming all three functions are positive valued). In formulas:
q(x) <= c max (f(x),g(x),h(x)) <= c (f(x) + g(x) + h(x)).
Proving the max rule for a fixed number of functions is pretty easy, once you see the pattern. However, proving the max rule for any number of functions using induction is a little harder--but not much.
2. Put these functions in order of increasing growth with the most slowly growing functions on the left. That is, put f(n) before g(n) if f(n) is O(g(n)). (n-2)!, 2^(2n), 0.0001n^4, n log n.
solution
n log n, 0.0001n^4, 2^(2n), (n-2)!.
There were two non-obvious things here. The first one you should all have known. The 0.0001 on the front of n^4 is irrelevant. Second, a factorial grows faster than an exponential. To see that a factorial grows faster than an exponential, recall that n! includes multiplication by n, n-1, n-2, all the way down to 1 and 2^n includes multiplication of 2 n-times. So in the factorial term, you multiply n terms, of which n-2 are geater than 2, and in the exponential term, you multiply n terms all of which are equal to 2.
3. What is the difference between "undecidable" and "NP-Complete"?
solution The difference is that "undecidable" means you can't solve it and "NP-complete" means is probably really hard to solve, but solvable given enough time.
This is an easy question designed to make sure people realize that NP-complete doens't mean undecidable. It just means really hard.
Posted by jones at 08:26 AM | Comments (1)