Problem Set 1: Cash

Evidence of a 5-point submission

• Getting cents: Should be done with a do-while loop, with an appropriately named cents variable declared but not defined before the start of the loop
  • We’re looking for int cents;, not int cents = 0;
• Coin calculations: All four of these should be one-liners, like return cents / 25;

Evidence of a 4-point submission

• Comparable to a 5-point submission but with one or two design mistakes, such as:
  • defining the cents variable in get_cents with a random magic number value before the do-while loop
  • If using separate calculate functions, making the calculate functions two-liners by storing cents / 25 in a variable and then returning that variable
  • making calculate_pennies return cents / 1 instead of just cents

Evidence of a 3-point submission

• Makes one or two more substantial mistake than the above, such as:
  • Getting cents: not using a do-while loop, or not providing get_int with an argument
  • Coin calculations: using a loop to calculate coins instead of a single division (in other words, any linear-time solution, since a constant-time solution is much preferred)

Evidence of a 2-point submission

• Makes more than one of the substantial mistakes described above for 3-point submissions
• Structure of the four calculate functions do not imply their similarity (students should notice these four functions require essentially identical implementations; if their code substantially differs for each, that’s worth pointing out)
• Solution suggests fundamental lack of understanding of provided code

Evidence of a 1-point submission

• Makes many substantial mistakes, suggesting a fundamental misunderstanding of the material (for instance, the functions might not return anything useful or relate to the distribution code in any coherent way)

Example Implementations (Worse vs. Better)

get_cents function

Worse Implementation

Vague variable name, magic number ‘0’, missed opportunity for do-while loop, no argument given to get_int:

int n = 0;
while (n < 0)
{
    n = get_int("");
}
return n;

Better Implementation

Clarifying variable name without initialization, do-while loop in proper context, helpful argument in get_int:

int cents;
do
{
    cents = get_int("Number of cents?: ");
}
while (cents < 0);
return cents;

calculate_quarters function

Worse Implementation

The $O(n)$ loop implementation:

int quarters;
do
{
    quarters = cents / 25;
    cents -= quarters * 25;
}
while (cents < 25);
return quarters;

Okay Implementation

Two-liner in $O(1)$:

int quarters = cents / 25;
return quarters;

Better Implementation

One-liner:

return cents / 25;