CS3230 AY 2025/26 Semester 2

Return to main page

Assignment #3 Statistics and Comments (T04)

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

General:

  • Your algorithm description should be clear enough for anyone to implement it. For example, when you say "split the range into four segments", you should clearly specify the indices of each segment. (E.g. For Q1(a), you may accidentally split a range of size 7 into segments of size 1, 1, 1, 4 instead of 2, 2, 2, 1.)
  • I would prefer pseudocode over paragraphs (except for dynamic programming solutions, which I will remind you later in the semester). However, your pseudocode does not have to be as verbose as actual code. Make good use of mathematical notations to simply it (e.g. maintain a range $(l, r)$ instead of writing assignment statements for $l$ and $r$) (e.g. writing the 4 cases in brackets instead of writing if-then-else).
  • Remember that time complexity analysis and proof of correctness is needed unless otherwise stated. If we didn't ask you to give a full proof of correctness, then some supporting arguments would be sufficient (but most likely, it's still based off an invariant / induction hypothesis.)

Q1:

  • We're asking for the exact number of queries needed (instead of an asymptotic bound). Marks are deducted for only proving the $\Theta(\log n)$ bound (instead of $\lceil \log_4 n \rceil$).
  • It's possible to do $\log_4 n$ instead of $\log_3 n$. The idea is to exploit all 4 possible outcomes of the 2 queries -- (True, False), (False, True), (False, False), (True, True). If you did $\log_3 n$, you will find yourself never using one of the outcomes.
    Also, you will notice that your part (b) algorithm will not terminate when $n = 4$. This should be apparent as you try to work out the base cases for your proof of correctness.
  • For part (b) proof of correctness, you should show clearly why the reduced problem has size strictly smaller than $n$ (i.e. why $\lceil n/4 \rceil + 2 < n$).
  • For part (b) query complexity analysis, you should state your bound clearly and show it (e.g. via expanding the recurrence, or induction). Some of you claimed a bound without proof.

Q2:

  • The algorithm has to be in $O(\log k)$. The key is to halve $k$ in each iteration / recursive call. Many incorrect attempts tried to reduce the range of the arrays, which did not guarantee a $O(\log k)$ time complexity.
  • If you did not provide a proof of correctness, I recommend you to try it out. The most important part is to show that the discard elements in $A$ (or $B$) can never be the $k$-th smallest element.

Q3: In general, many of the proofs are not very rigorous.

  • Many of you used informal terms / intuitions. For example, some of you wrote "the largest element in $A[1]$ to $A[n - i + 1]$ is moved to the right" (to where?). You should define the expected progress (where it has been moved to) explicitly, in mathematical notation in terms of $i$ and $j$.
  • Remember that you are ultimately doing a proof by induction. Therefore, in the maintenance step, you should start by assuming the invariant holds before the current iteration. If you never quoted this fact, then something should be wrong with your proof.
  • On how to formulate the loop invariant: Notice that this is actually bubble sort, moving the $i$-th largest element to the back in iteration $i$. Hence, the outer loop invariant should be on the expected progress of moving the $i$ largest elements. The inner loop aims to move the largest element to the $n-i+1$-th position, so it should be on the progress of moving that particular element. (There are two ways to write it out: Either "$A[j + 1] \geq A[1 \ldots j + 1]$ after the $j$-th iteration" or "The maximum element $A[k]$ in $A[1 \ldots n-i+1]$ is at position $\max\{k, j + 1\}$ after the $j$-th iteration".)
  • Order the proof to reflect the execution order (so your logic "flows"). So, the proof should be ordered as follows: 
    // invarant 1: initialization
for (...) // inner loop {
    // invarant 2: initialization
    for (...) // outer loop {
        // invarant 2: maintenance
    }
    // invariant 2: termination => invarant 1: maintenance
}
// invariant 1: termination
Last updated: 09 February 2026