Problem Set 3: Runoff

Evidence of a 5-point Submission

  • Each function—except tabulate, which iterates over voter_count and candidate_count—iterates over candidate_count. Where applicable, student uses the ! operator to check if a candidate has been eliminated.
  • vote uses strcmp to compare the candidate name to the input name
    • Uses the ++ operator
    • Includes a short-circuiting return statement within the for loop
  • tabulate function uses a variable to store preferences[voter][rank] (since it is referenced more than once). Also uses the ++ operator to increment the vote and the break keyword to short-circuit,
  • print_winner prints the candidate if they have more than (voter_count / 2), and uses return to short-circuit
  • find_min function initializes a min counter variable to a logical value (INT_MAX, MAX_VOTERS, etc.) which is explained with a comment, then updates min counter by comparing against each candidate’s votes, checking for candidate elimination in the same condition using &&
  • is_tie function checks if a candidate has more than minimum votes and is not eliminated (in a single condition using &&). Short-circuits when a match found
  • eliminate function checks if any candidate’s votes == min, eliminating that candidate if so

Evidence of a 4-point Submission

Follows the general approach of the 5-point submission with a few smaller design flaws (some listed below)

  • print_winner function may unnecessarily round (voter_count / 2).
  • is_tie function may check if a candidate has != min votes (> would be more appropriate)
  • find_min function may initialize the minimum voter count to a value like voter_count (a number of votes that some candidate could possibly receive), or a value that is not explained with a comment
  • May include unnecessary return statements in void functions

Evidence of a 3-point Submission

  • Each function—except tabulate, which iterates over voter_count and candidate_count—iterates over candidate_count at most once.
  • vote uses strcmp to compare the candidate name to the input name; short-circuits when a match is found.
  • tabulate function updates the vote and uses the break keyword to short-circuit,
  • print_winner compares votes to (voter_count / 2), either rounded or unrounded.
  • find_min function initializes a min counter variable to a reasonable number
    • May not explained with a comment
    • Could be a number of votes that some candidate could possibly receive.
  • is_tie function short-circuits when a match found
  • eliminate function checks if any candidate’s votes <= min (the less-than is unnecessary by definition of min)

Evidence of a 2-point Submission

  • Does not short circuit in functions that should short-circuit (vote, print_winner, is_tie)
  • vote function may unnecessarily check if the candidate has been eliminated
  • eliminate function includes unnecessary steps (setting votes of an eliminated candidate to zero)

Evidence of a 1-point Submission

  • Does not store the index of the candidate in the preferences array (stores the name, instead)
  • vote function may not use the strcmp function
  • Functions do not iterate over candidate_count

Example Implementations (Worse vs. Better)

vote Function

Worse Implementation

The example below unnecessarily checks if a candidate has been eliminated (the vote function is exclusively called before any elimination happens)

for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].eliminated != true && strcmp(candidates[i].name, name) == 0)
    {
        preferences[voter][rank] = i;
        return true;
    }
}
return false;

Better Implementation

The example short-circuits when a match is found, using no extraneous comparisons or variables

for (int i = 0; i < candidate_count; i++)
{
    if (!strcmp(name, candidates[i].name))
    {
        preferences[voter][rank] = i;
        return true;
    }
}
return false;

tabulate Function

Worse Implementation

The example below unnecessarily initializes the candidates’ vote count to zero (this is done in the main function), uses a do-while loop instead of a for loop, and does a confusing computation to short-circuit (j = candidate_count) instead of using the break keyword. Additionally, the example uses a return statement when none is necessary.

for (int i = 0; i < candidate_count; i++)
{
    candidates[i].votes = 0;
}

for (int i = 0; i < voter_count; i++)
{
    int j = 0;
    do
    {
        if (candidates[preferences[i][j]].eliminated == false)
        {
            candidates[preferences[i][j]].votes++;
            j = candidate_count;
        }
        j++;
    }
    while (j < candidate_count);
}

return;

Better Implementation

The example below uses the ! operator, as well as the ++ operator. Additionally, since preferences[i][j] is referenced more than once in the function, a variable is used to hold each value

for (int i = 0; i < voter_count; i++)
{
    for (int j = 0; j < candidate_count; j++)
    {
        int preference = preferences[i][j];
        if (!candidates[preference].eliminated)
        {
            candidates[preference].votes++;
            break;
        }
    }
}

Worse Implementation

The example below uses a method that will not short-circuit. Additionally, the example rounds voter_count / 2 (this extra computation is not necessary)

int highest = 0;
int index;

for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].votes > highest)
    {
        highest = candidates[i].votes;
        index = i;
    }
}

if (highest >= round(voter_count / 2))
{
    printf("%s\n", candidates[index].name);
    return true;
}
return false;

Better Implementation

The example below will short-circuit and will not round unnecessarily

for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].votes > voter_count / 2)
    {
        printf("%s\n", candidates[i].name);
        return true;
    }
}

return false;

find_min Function

Worse Implementation

The example below includes an unnecessary second conditional statement

int min_votes = voter_count;
for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].eliminated == false)
    {
        if (min_votes < candidates[i].votes)
        {
            min_votes = candidates[i].votes;
        }
    }
}

return min_votes;

Better Implementation

The example below uses a value for the starting minimum vote count that no candidate could possibly have. Also uses the && and ! operators

int min = MAX_VOTERS + 1;
for (int i = 0; i < candidate_count; i++)
{
    if (!candidates[i].eliminated && candidates[i].votes < min)
    {
        min = candidates[i].votes;
    }
}
return min;

is_tie Function

Worse Implementation

The example below does not short-circuit

int count = 0;
int running = 0;
for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].eliminated == false && candidates[i].votes == min)
    {
        count++;
    }
    if (candidates[i].eliminated == false)
    {
        running++;
    }
}

if (count == running)
{
    return true;
}
return false;

Better Implementation

The example below uses the ! and && operators, short circuits when a tie is found, and compares the number of votes to the min vote count using the > operator

for (int i = 0; i < candidate_count; i++)
{
    if (!candidates[i].eliminated && candidates[i].votes > min)
    {
        return false;
    }
}
return true;

eliminate Function

Worse Implementation

The example below uses an unnecessary extra conditional. It is also unnecessary to check if the votes are <= min (only == min is necessary here)

for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].votes > min)
    {
        continue;
    }
    else if (candidates[i].votes <= min)
    {
        candidates[i].eliminated = true;
    }
}

Better Implementation

The example below does not include an unnecessary conditional or return statement

for (int i = 0; i < candidate_count; i++)
{
    if (candidates[i].votes == min)
    {
        candidates[i].eliminated = true;
    }
}