Well, let’s say that you guessed the answer and then verified that it works. I’d like to see that verification. If you used the master theorem statement, then showing this is sufficient. If you had to unroll a recurrence, then I’d want to see how you did it. and so on
basically, whatever scratch work you did to convince yourself (think of me as the verifier verifying your proof :))
On the 3SAT problem…suppose my algorithm runs faster when m = 1 as opposed to m = 2, so technically the number of clauses does matter, but it’s still got this nice 2^n feel. Is that okay? Or must it be that m strictly does not matter?
Also, what if some clause is:
(x1 OR x1 OR !x1)
Doesn’t this break down and we’re setting v1 to false and v2 to true (and v1 == v2)?
Can we just assume that within each clause there are distinct literals?
I’m not sure what you mean by a 2^n feel. your algorithm must be better than 2^n (strictly). It turns out that for the method of analysis we are using, m doesn’t matter, because the dependence on m is polynomial.
Also, you can assume w.l.o.g that each clause has distinct literals.
In the FFT notes, I think I’m missing something.
In Algorithm 1 (Recursive FFT), the input is of length n, and the output is of length 2n.
This seems handy when we’re going from 4 coefficients to 8 points, but there’s a decent level of badness when doing the reverse (when we want to go from 8 points to 8 coefficients).
Also, in the wiring diagram, the input and output vectors both have length 8, not 4 and 8.
Are we just supposed to pad the coefficients with extra 0’s? And if that’s the case, why the difference between the pseudo-code and wiring diagram?
Thanks for any information.
Ah. This is indeed a problem. the wiring diagram is correct (with 8 wires). What is wrong is that in the pseudocode, I should have added the padding in, to make the input of size 2n rather than n. Specifically, the first line of the pseudocode should read
Input: a = (a_0, a_1, …, a_{2n-1})
Thanks for catching this.
p.s if you do this, the wiring diagram behaviour matches the pseudocode.
Entries
September 20th, 2007 at 10:06 am
On problem 1.1, how detailed must the answers be? (i.e., what do we need beyond just T(n) = theta(…)?)
September 20th, 2007 at 1:01 pm
Well, let’s say that you guessed the answer and then verified that it works. I’d like to see that verification. If you used the master theorem statement, then showing this is sufficient. If you had to unroll a recurrence, then I’d want to see how you did it. and so on
basically, whatever scratch work you did to convince yourself (think of me as the verifier verifying your proof :))
September 21st, 2007 at 2:54 pm
On the 3SAT problem…suppose my algorithm runs faster when m = 1 as opposed to m = 2, so technically the number of clauses does matter, but it’s still got this nice 2^n feel. Is that okay? Or must it be that m strictly does not matter?
Also, what if some clause is:
(x1 OR x1 OR !x1)
Doesn’t this break down and we’re setting v1 to false and v2 to true (and v1 == v2)?
Can we just assume that within each clause there are distinct literals?
September 22nd, 2007 at 1:23 am
I’m not sure what you mean by a 2^n feel. your algorithm must be better than 2^n (strictly). It turns out that for the method of analysis we are using, m doesn’t matter, because the dependence on m is polynomial.
Also, you can assume w.l.o.g that each clause has distinct literals.
September 22nd, 2007 at 7:25 pm
In the FFT notes, I think I’m missing something.
In Algorithm 1 (Recursive FFT), the input is of length n, and the output is of length 2n.
This seems handy when we’re going from 4 coefficients to 8 points, but there’s a decent level of badness when doing the reverse (when we want to go from 8 points to 8 coefficients).
Also, in the wiring diagram, the input and output vectors both have length 8, not 4 and 8.
Are we just supposed to pad the coefficients with extra 0’s? And if that’s the case, why the difference between the pseudo-code and wiring diagram?
Thanks for any information.
September 22nd, 2007 at 10:22 pm
Ah. This is indeed a problem. the wiring diagram is correct (with 8 wires). What is wrong is that in the pseudocode, I should have added the padding in, to make the input of size 2n rather than n. Specifically, the first line of the pseudocode should read
Input: a = (a_0, a_1, …, a_{2n-1})
Thanks for catching this.
p.s if you do this, the wiring diagram behaviour matches the pseudocode.