CS3230 AY 2025/26 Semester 2

Return to main page

Assignment #5 Statistics and Comments (T04)

The average score in our class is 7.95 / 8. Well done! Below are the statistics for each question:

Nothing much to say here, just read the short comments I might have left on your script.

For Q1, most solutions use recurrences and solved a system of linear equations. Alternatively, it is possible to just use a sum of geometric series to solve the problem. WLOG suppose the first step is $0 \to 1$. Then, all good outcomes must be in the form $0 \to 1 \to 0 \to 1 \to \cdots \to 0 \to 2$, which occurs with probability $\dfrac{1}{4} + \dfrac{1}{4^2} + \dfrac{1}{4^3} + \cdots = \dfrac{1/4}{1 - 1/4} = \dfrac{1}{3}$.

These are some notes I left for Question 2 for the previous batch (if you are interested). I don't see some of these mistakes this year (Good job!).

  • Question 2(a) is just a simple exercise on how to write rigorous proofs (a preparation for the midterm test!). While we're not requiring you to explicitly cite everything you quoted and number your proofs (that will be tragic), we still expect your proofs to be rigorous (not to skip any essential arguments). Here is a common mistake:
    • Some students rephrases the definition of $v_i \in I$ to "all neighbours of $v_i$ appear after $v_i$".
    • Taking the definition of $v_i \in I$ literally, it actually means "all vertices $v_j$ appearing before $v_i$ are not neighbours to $v_i$". This is actually a contrapositive to the original definition, assuming there are no self-loops in the graph.
    • If you would like to use the repharsed definition, you should show why they are equivalent.
    Some students also wrote way more than necessary (e.g. by using induction). In this problem, a direct proof suffices - I'm just looking for how you linked the definition of an independent set to the definition of $I$.
  • Remarks on two proving tools:
    • Without loss of generality (WLOG): This is a useful tool to eliminate symmetric cases. Instead of enumerating the two cases $i < j$ and $i > j$, you can simply write "WLOG suppose $i < j$" and only handle the case $i < j$ later on. Make sure that the case $i > j$ is completely symmetric, though.
    • Proof by contradiction: I believe you are familiar with this, but many of you did not state where the contradiction occurs on your proof. That makes your proof hard to follow.
  • Question 2(b) is well-done.
    • Great that many students showed very clearly how they defined the indicator random variables and applied linearity of expectation!
    • The fact that $\mathbb{P}[X_v = 1] = \frac{1}{d(v) + 1}$ could be explained by the fact that all $d(v) + 1$ vertices (vertex $v$ and its neighbours) have an equal chance of being placed first (relatively), since all $(d(v) + 1)!$ relative orderings are equally likely in a random permutation. There's no need to compute the number of permutations to attain this conclusion (you will be wasting time if you do this in the midterm test).
  • Question 2(c) is a straightforward application of the probabilistic method. But many of you didn't mention that $I$ is an independent set - I didn't penalize that for this assignment. The intended argument should be:
    • Since $\mathbb{E}[I] = \frac{1}{d(v) + 1}$ for a random ordering of the vertices, there exists an ordering of the vertices such that $|I| \geq \frac{1}{d(v) + 1}$.
    • This set $I$ is an independent set by part (a).
Last updated: 23 February 2026