CS3230 AY 2025/26 Semester 2

Return to main page

Assignment #4 Statistics and Comments (T04)

The average score in our class is 7.7 / 8. Below are the statistics for each question:

Overall the assignment is well done. Some quick remarks.

  • Q1: While the proof structures are generally good, some missed the essential arguments that I'm looking for.
    • Step 2-3: What does the final value of count[] represent?
      The pseudo-code is quite trivial so we do not expect a proof here -- you can jump directly to the conclusion.
    • Correctness: Why are the values stored correctly? Let's say we put the value A[i] into count[A[i]], why is it "placed correctly"? (To show this, we must show that in an ideal sorted array, the index count[A[i]] indeed contains A[i].)
    • Correctness: Why is the array filled at the end? Is it possible that some indices of B are never filled?
    • Stability: You must mention that count is monotonically decreasing. As count decreases by at least once and never increases back, the subsequently processed entries with the same value must be placed earlier in B.
    These are what we mean by "arguments", and they must be present regardless of your method of presentation (e.g. using invariants). (Basically, think of fundamental reasons/intuitions why the algorithm is correct.)
  • Q2: You don't have to reinvent the wheel (e.g. implementing counting/radix sort or proving their correctness). However, the "proof of correctness" we're looking for is a proof that your algorithm sorts the values $n^y \cdot x$ correctly. This should fall into 3 cases:
    • If $y_1 \leq 3$ and $y_2 \geq 4$, then $val(x_1, y_1) < val(x_2, y_2)$.
    • If $y_1, y_2 \geq 4$ and $y_1 < y_2$, then $val(x_1, y_1) < val(x_2, y_2)$.
    • If $y_1, y_2 \geq 4$, $y_1 = y_2$ and $x_1 < x_2$, then $val(x_1, y_1) < val(x_2, y_2)$.
    Each of which should involve an inequality chain.
  • Q3: The solution is in this video.
    If you did not come up with the solution on your own, you should try to derive it again. The idea is that you should try your best to divide the 24 outcomes into 3 equal groups, depending on the result of the weighing.
    P.S. Some of you missed the lower bound proof.
Last updated: 16 February 2026