Just curious.. For our final grades, would you be considering the average of ALL homeworks or would we have one get-out-of-jail-free card - if you’d be considering something like the 5 best scores?
I had mentioned in class (although I can’t find it on the website) that there’s one get-out-of-jail-free card. The worst score (with the exception of Homework 0) will be dropped
For problem 5.4 (which is 13.14), Part (a) - Do we need to give a proof or is it sufficient to provide an example where no perfectly balanced partition of processes is possible?
Well you have to show me that the example does show what I’d expect it to show (i.e no balanced partition). if that’s obvious from the nature of the example, then fine, else I need to be convinced. Remember, I am a skeptical poly-time verifier.
Long answer: I’m not sure why that is relevant. The problem in 5.4 is to figure out an assignment that’s good for each job separately (ie is nearly balanced). The balance is with respect to the job J(i), rather than “current load on the machine”. So if you wanted to pretend that each job is run separately, that’s fine, but it’s irrelevant to the question being asked.
For problem 5.2, should there not be a constant c for any e (not just e > 0)?
With this said, does it make any sense to have assignments to e that are outside the range [0,1]?
For the probability of the boolean statement (Xh - Xt > c*sqrt(n)) is clamped to the range [0,1], correct?
If both these are correct, then should there not be a positive AND negative constant value c for each value of e?
Well, it’s impossible to assign a constant for the case e = 0, because even a heavily skewed assignment is possible with some nonzero probability. What will happen is that the value of c will grow without bound as e tends to zero.
In general, it does not make sense to set epsilon to be more than 1, yes.
If you’re asking whether there should be a corresponding upper bound for the Pr(Xh - Xt c*sqrt{n})), which requires different kinds of arguments.
Thanks. Hmmm… perhaps I am not able to comprehend the problem well. Suppose, for a moment, we don’t think of randomizing the assignment. Then essentially, this translates to figuring out an assignment of all the ‘k’ basic processes (which is the universal set P, where k>2n) to either M1 or M2. And we’d like to do so in a way which “nearly balances” some n subsets of P (where each subset has size 2n).
In other words, if we adopt a deterministic approach, then this assignment of k processes to 2 machines would have been determined once at the start only. And then all n jobs would run their 2n processes according to that mapping??
In other words, if we adopt a deterministic approach, then this assignment of k processes to 2 machines would have been determined once at the start only. And then all n jobs would run their 2n processes according to that mapping??
Yes, that’s exactly right. And in the randomized case, all that changes is that the assignment is determined in a randomized machine. It is still determined at the start.
Again, for 5.2:
You say it is impossible to assign a constant value to c when e = 0,
well you can assign c to 2*sqrt(n) and this will make the boolean statement always false, correct? however you can also assign anything greater than 2*sqrt(n) and this is why we cannot assign a ‘constant’ value, correct?
Well if this is the case for the ‘upper bound’ for assigning a constant to c (’lower bound’ for e), then the ‘lower bound’ for assigning a constant value to c should also be present (this is an assumption, not a logical connection) Investigating if there is actually a ‘lower bound’ one will find -2*sqrt = c. This is the ‘upper bound’ for e, 1, which means that it is always possible. This makes sense, for if we have any c less than -2*sqrt(n), then the statement is always true. If this is in fact the case, I can’t prove that for any e > 0, there exists a constant c for the provided statement. For there is not a single constant value for c when e >= 1.
Where has my logic been lost?
In problem 5.5 (13.16 in the text) must k be a function of n? Can k be a constant?
Also, does the probability of B being correct have to be 9/10 or can it be greater?
Regarding 5.2, as I said earlier, assume that e = 1 (which doesn’t make any sense anyway).
Regarding 5.5, you can solve for any k you want, as long as you get the desired bound. And to answer the second part of the question, the probability of success can be at least 9/10.
p.s it helps me if you post some identifying marker as your ID, rather than Anonymous. You don’t need to post your name: merely something that allows me to connect the various conversation threads together.
Can we assume any strategy we like(that simplifies the math rather than being optimal) that the receivers use collaboratively to produce $\beta$? If not, is the closed form for $k$ a must?
Entries
November 25th, 2007 at 11:09 pm
Just curious.. For our final grades, would you be considering the average of ALL homeworks or would we have one get-out-of-jail-free card - if you’d be considering something like the 5 best scores?
November 25th, 2007 at 11:26 pm
I had mentioned in class (although I can’t find it on the website) that there’s one get-out-of-jail-free card. The worst score (with the exception of Homework 0) will be dropped
November 25th, 2007 at 11:38 pm
Great news! Thanks so much..
November 27th, 2007 at 6:15 pm
Could you post hw4’s stats? Thanks
November 27th, 2007 at 10:25 pm
hw4 isn’t graded yet. I’ll post HW3 stats right now.
November 28th, 2007 at 5:59 pm
For 5.1(b), we need to find the expectation with respect to the scheme in 5.1(a)?
November 28th, 2007 at 9:41 pm
Yes, that is correct. Remember that the probability of H is some p not equal to 0.5
December 1st, 2007 at 11:28 am
For problem 5.4 (which is 13.14), Part (a) - Do we need to give a proof or is it sufficient to provide an example where no perfectly balanced partition of processes is possible?
December 1st, 2007 at 12:20 pm
Well you have to show me that the example does show what I’d expect it to show (i.e no balanced partition). if that’s obvious from the nature of the example, then fine, else I need to be convinced. Remember, I am a skeptical poly-time verifier.
December 2nd, 2007 at 2:59 pm
5.4 (or 13.14): Am I correct in assuming that a job J(i) cannot be started until all the 2n basic processes of the previous job J(i-1) finish?
December 2nd, 2007 at 3:15 pm
Short answer: yes
Long answer: I’m not sure why that is relevant. The problem in 5.4 is to figure out an assignment that’s good for each job separately (ie is nearly balanced). The balance is with respect to the job J(i), rather than “current load on the machine”. So if you wanted to pretend that each job is run separately, that’s fine, but it’s irrelevant to the question being asked.
December 2nd, 2007 at 4:57 pm
For problem 5.2, should there not be a constant c for any e (not just e > 0)?
With this said, does it make any sense to have assignments to e that are outside the range [0,1]?
For the probability of the boolean statement (Xh - Xt > c*sqrt(n)) is clamped to the range [0,1], correct?
If both these are correct, then should there not be a positive AND negative constant value c for each value of e?
December 2nd, 2007 at 4:57 pm
Did that go through?
December 2nd, 2007 at 5:17 pm
Well, it’s impossible to assign a constant for the case e = 0, because even a heavily skewed assignment is possible with some nonzero probability. What will happen is that the value of c will grow without bound as e tends to zero.
In general, it does not make sense to set epsilon to be more than 1, yes.
If you’re asking whether there should be a corresponding upper bound for the Pr(Xh - Xt c*sqrt{n})), which requires different kinds of arguments.
December 2nd, 2007 at 5:24 pm
Thanks. Hmmm… perhaps I am not able to comprehend the problem well. Suppose, for a moment, we don’t think of randomizing the assignment. Then essentially, this translates to figuring out an assignment of all the ‘k’ basic processes (which is the universal set P, where k>2n) to either M1 or M2. And we’d like to do so in a way which “nearly balances” some n subsets of P (where each subset has size 2n).
In other words, if we adopt a deterministic approach, then this assignment of k processes to 2 machines would have been determined once at the start only. And then all n jobs would run their 2n processes according to that mapping??
December 2nd, 2007 at 5:27 pm
In other words, if we adopt a deterministic approach, then this assignment of k processes to 2 machines would have been determined once at the start only. And then all n jobs would run their 2n processes according to that mapping??
Yes, that’s exactly right. And in the randomized case, all that changes is that the assignment is determined in a randomized machine. It is still determined at the start.
December 2nd, 2007 at 5:49 pm
Again, for 5.2:
You say it is impossible to assign a constant value to c when e = 0,
well you can assign c to 2*sqrt(n) and this will make the boolean statement always false, correct? however you can also assign anything greater than 2*sqrt(n) and this is why we cannot assign a ‘constant’ value, correct?
Well if this is the case for the ‘upper bound’ for assigning a constant to c (’lower bound’ for e), then the ‘lower bound’ for assigning a constant value to c should also be present (this is an assumption, not a logical connection) Investigating if there is actually a ‘lower bound’ one will find -2*sqrt = c. This is the ‘upper bound’ for e, 1, which means that it is always possible. This makes sense, for if we have any c less than -2*sqrt(n), then the statement is always true. If this is in fact the case, I can’t prove that for any e > 0, there exists a constant c for the provided statement. For there is not a single constant value for c when e >= 1.
Where has my logic been lost?
December 2nd, 2007 at 6:15 pm
In problem 5.5 (13.16 in the text) must k be a function of n? Can k be a constant?
Also, does the probability of B being correct have to be 9/10 or can it be greater?
December 2nd, 2007 at 7:17 pm
Regarding 5.2, as I said earlier, assume that e = 1 (which doesn’t make any sense anyway).
Regarding 5.5, you can solve for any k you want, as long as you get the desired bound. And to answer the second part of the question, the probability of success can be at least 9/10.
December 2nd, 2007 at 7:18 pm
p.s it helps me if you post some identifying marker as your ID, rather than Anonymous. You don’t need to post your name: merely something that allows me to connect the various conversation threads together.
December 3rd, 2007 at 2:53 am
Can we assume any strategy we like(that simplifies the math rather than being optimal) that the receivers use collaboratively to produce $\beta$? If not, is the closed form for $k$ a must?
December 3rd, 2007 at 2:55 am
Part of the problem is to find a reasonable strategy. It doesn’t have to be optimal, as long as you can show the desired bound.