CS3230 AY 2025/26 Semester 2

Return to main page

Assignment #6 Statistics and Comments (T04)

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

Those who followed my advice (the answering guide and the sample) did quite well. For those who didn't, please check out my grading remarks and reach out to me if you have any questions. (I won't include those in the common mistakes since it would confuse the other students.)

Grading Remark: Q1a is based on your state, Q1b is based on your recurrence and base cases, and Q1c is based on your algorithm (computation order) & time complexity analysis.

Some reminders and common mistakes:

  • State: Please make sure your state corresponds to your base cases and recurrences. E.g. for knapsack, depending on whether you restrict the weight to be exactly $w$ or at most $w$, your base cases and recurrences would be different.
  • Recurrences: Some did not state the bounds clearly, or missed some important constraints.
  • Missing base cases. Remember that you must ensure that your recurrence always map to some base cases, in Q1, you should define all $dp(0, *)$ that are used in the recurrences for $dp(1, *)$. A correct answer is:
    • $dp(0, 0) = \text{true}$
    • $dp(0, s) = \text{false}$ for all $s > 0$
    It's preferrable that you don't include extra base cases (e.g. $dp(*, 0)$), as long as it's not used by the recurrences. (Otherwise, it would be confusing for the grader.)
  • Algorithm to compute the answer: A lot of you missed that (I don't know why). It should be very simple to explain in one or two sentences (again, pseudo-code is not needed).
    Don't forget to state where you could find the answer (e.g. $dp(n, w, r)$ for Q3).
  • Time complexity analysis: You MUST explain (1) the number of distinct states, and (2) the time needed to compute the recurrence of each state. For this problem, you must state that computing the recurrence takes $O(1)$ time.
Last updated: 09 March 2026