Problem 1 (Zach) 4+3 points
For problem 1, the biggest problem I saw was that in the equation x_i + x_j = b_r mod 2, many people thought that b_r was randomly chosen.
b_r was, however, fixed and thus your sample space should have four elements in it (namely (x_i, x_j) = (0,0), (0,1), (1,0), (1,1)) instead of eight.
Problem 2 (Kevin and John) 2+2+2 points (parts d. and e. cancelled)
(John) We only graded parts a,b,c (not grading d and e). On these three it seemed people either got them right, or made the wrong assumptions. Really, the main pitfall of this problem was simply not getting ones head around all the assumed properties.
(Kevin) Due to a confusion in office hours regarding part (d) (and the dependence of your answer on part (e) on your answer for part (d)), we decided to only grade parts (a), (b), and (c) of this problem. The most common mistake for part (a) was to neglect that alpha is being randomly chosen, and you were meant to give the probability that (f_alpha(x) = k) where alpha was chosen from a uniform distribution. Thus, your counter-example cannot be the case when "alpha = 0". Some people did not realize that when (x = 0), the value of f(x) is always 0, so the probability that it equals some given k will never be 1/p. The same two mistakes were also made in parts (b) and (c).
Problem 3 (Hari) 3 points
The main problem with this problem was that some people decided to prove Markov's inequality. Also, lots of people picked a value for mu and/or k and made a random variable for this. When a problem says "given a value of mu and k" that means you can assume that you know what the values are, not that you can pick specific ones.
Problem 4 (Joel) 3 points
The most common mistake on problem 4 was to incorrectly assume that V(cX) = cV(x) rather than V(cX) = c^2V(X). This would cause you to mistakenly conclude that the two standard deviations were equal, rather than off by a factor of 1 over sqrt 2.
Problem 5 (Tom) 3 points
Almost everyone got this question right. Many people did not mention anywhere in their proof that X and Y were independent -- you lost a point if you said E(XY)=E(X)E(Y) without mentioning that X and Y are independent. Also, it is true that if X and Y are independent, then X+a and Y+b are independent, but you needed to mention this or you lost points.
Problem 6 (Yogi) 0/1 points--Optional Problem
Unfortunately, nobody got this problem right. Even more unfortunately, very few students even tried to attempt the problem. Due to very few attempts, I happened to see very few frequent mistakes, which I summarize as follows:
Many students (or almost all student who tried the problem) misunderstood the problem as analyzing the running time on a random input (coming from, say, a uniform distribution). This was not the case. The input was supposed to be fixed assignment to the variables and the randomization came into picture only because the algorithm is allowed to choose randomly which side to evaluate first. So, for any fixed input, the expected number of variables seen is 3^n. Even when students tried to bring the random assignment (input) into picture, they did not analyze the algorithm satisfactorily and hence did not get the credit (the problem is 0/1).
I cannot overemphasize the importance of writing your arguments cleanly and understandably. Many times, students said that on an average, the algorithm will check 3 variable out of four variable, without any justification. Remember, you get full credit only if you justify your steps and just correct answer does not ensure you full credit (unless specified otherwise). So, always justify your steps.
Problem 1 (2+1) John
The majority of the mistakes on this problem came about from failing to prove the distribution worked for all sigmas, ks etc. Apart from that people did quite well.
Problem 2 (1+2+3) Zach
I don't have any comments, most people did the problem correctly but might have lost for minor mistakes.
Problem 3 (3+2) Yogi
Most of the students got the idea behind the problem right. One common misunderstanding (and indeed, ambiguity in the statement of the problem) was whether to take the span of $(nt-1)$ intervals without any requests or span of $nt$ requests. The solution says that we take $nt-1$ interval span of no requests, but we also accepted the solutions with $nt$ span. But one caveat with span of $nt$ slots is that the expected waiting time does not turn out to be nice $n/\lambda$ slots, but it comes out to be $n/\lambda*(1-\lambda/n)$. If you took the span to be $nt$ and gave the expected time for $nt-1$ slots, you lost one point for that.
One other common mistake was to give the expected number of slots ($n/\lambda$) instead of expected number of waiting hours ($1/\lambda$). You did not loose any points for this mistake, although one of the point of the problem was to illustrate that the expected number of hours does not depend on $n$.
Problem 4 (2+2+3) Tom
The biggest problem that I saw was people who weren't careful and ended up off-by-one. The first term in the sum for (a) was 1/j, not 1/j+1. For similar reasons, the second part ended up as (j-1)/(n-1), not j/n. Apart from this, many people somehow got an answer for (c) which included the variable j. It is impossible that this variable appears in the solution: j was an arbitrary user, and part (c) asks for the expectation over all users. If your answer to part (b) was incorrect, but your answer to (c) followed from it, you did not lose points for (c).
Problem 5 (3) Kevin
By far, the most common error was to say that there are n vertices, and only (n-1) choices for degree, and thus by the Pigeonhole Principle, two vertices must share a degree. However, there are actually n choices for degree when you consider that a vertex can have degree zero. A two-point penalty was incurred for this oversight.
Some people gave the trivial counter-example of when there is only 1 vertex. This trivializes the problem, and without further discussion, zero points were awarded for this solution.
Problem 6 (3) Kevin
Almost everyone got this correct. The only mistakes were misinterpretations of the claim to mean that there must be an edge between all pairs of vertices, and inadequate case analyses (missing one or more cases of graphs).
Problem 7 (0/1) Tom
Almost everyone who attempted this problem solved it correctly (though there were multiple solutions which we accepted). The correct answer depends on your interpretation: does everyone flip simultaneously, or can the last flipper see what everyone else got before he reports his answer? In the first case, it's possible to ensure a completely random result, while in the second case you can only force the cheater's effect to be arbitrarily small. [The hint in the problem goes with the latter interpretation.] Both interpretations were accepted.
Problem 1 (2+3+2+1) Yogi
Most of the students got the problem right... but many of them were not precise enough, in the sense that they did not define the random variables correctly and worked around the problem in an intuitive way. For example, in part (c), you could say that the probability of one node having degree greater than (k+1)\times\mu is q (some quantity q) and then say that the expected number of nodes having degree greater than (k+1)\times\mu is n\times q. Its good to think about the problem this way, but while writing up the solutions, I would suggest you define a 0/1 random variable Y_u for each node u which takes value 1 if degree of u is greater than (k+1)\times\mu and 0 other wise, compute the expectation and then sum up the expectations for all nodes (using linearity of expectation). But, of course, no points were taken off for the lack of all this.
Specific comments for all parts follow:
Let N={n \choose 2}. Some students forgot to multiply p^{m}\times(1-p)^{N-m} by {N\choose m} (which is the number of ways of choosing m edges from N possible edges). Some students wrote {n\choose m} instead of {N\choose m}. Typically you lost one point for this mistake but if there were some more problems with the form of the answer, you might have lost 1.5 points.
Most of the students got explanation for the expectation right and got the variance right. The only mistake was (if any) was playing with the constants in the Chebyshev's inequality. For mistakes in the algebra/wrong manipulation of inequalities, you lost one point.
Most students got the step of multiplying the answer to part (b) by n right. But upper-bounding this by \frac{1}{k^2 p} was the common problem. Some of them just wrote that n\times answer to part (b) is less than \frac{1}{p k^2} without any justification. You lost one point for lack of justification (unless it was pretty obvious from your final expression).
I remember just a couple of students getting this wrong (although some students forgot to attempt this part). Some of them wrote the following intuitive argument: If the edge between v and w is there, it increases the expected degree of both and if the edge is not there, it decreases the expected degree of both the vertices. Hence the variables are not independent. Please note that this is not enough. It is important to think about the problem this way, but the final answer should compute the actual expectations and probabilities (and show that they are not equal). The most straight forward thing was to say that probability of v's degree being 0 and w's degree being n-1 (simultaneously) is zero but their individual probabilities are not zero, and now it follow from the definition of independence (Pr[A\and B]=Pr[A]\times \Pr[B]) that the two random variables are not independent.
Problem 2 (2+2) Joel
The problem with the proof was not that it mentioned simple graphs while the statement of the problem did not. That was just a minor oversight in the problem statement, as there was something more fundamentally wrong with the proof.
Furthermore, the flaw with the proof was not that it "didn't account for disconnected graphs" That's more of a characterization of what it missed. The real issue is that there was a flaw in the buildup argument in the inductive step, as it is not true that all graphs that satisfy the property on n nodes can be constructed from a graph that satisfied the property on n-1 nodes.
Problem 3 (4) Hari
For the most part people understood the two cases necessary and did the arithmetic correctly. However, some people did induction on the number of leaves instead of the number of nodes. While this can be done correctly, most people did it incorrectly.
Problem 4 (4) John
People did quite well on this problem. The main serious error was people failing to find an appropriate geometry, while more commonly people lost a point for not including calculations showing their assertions were correct.
Problem 5 (2+3) Tom
Problem 6 (4) Kevin
Nearly every student got the right idea for this problem; some people just make their proof clear enough. Everyone argued either in terms of 2 necessary paths or needing 2 nodes per level in the BFS tree. Some people used the "levels" argument without defining what their levels were, or incorrectly defining them. Minor errors like this lost 1 point.
Problem 7 (0/1) Kevin/Tom