Problem Set 3: Tideman

Evidence of a 5-point Submission

• vote function iterates over candidate_count at most once, using strcmp to check if a candidate’s name is valid and short-circuiting with return true if so
• record_preferences and add_pairs function uses a nested for loop, with the inner for loop starting its indexing at the index of the outer loop + 1, uses the ++ operator
• sort_pairs function uses a sorting algorithm that can run better than candidate_count² iterations (for example, bubble sort that breaks once elements are sorted)
• lock_pairs function uses helper functions which short-circuit
• print_winner function short-circuits

Evidence of a 4-point Submission

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

• May check if a variable is false in a conditional using the == false comparison instead of the ! operator
• May use a sorting algorithm that is no better than candidate_count² iterations (for example, bubble sort but without an optimization to stop once elements are sorted)
• lock_pairs function and its helper functions may use extra conditionals

Evidence of a 3-point Submission

• vote function iterates over candidate_count at most once, short-circuiting when a name match is found
• record_preferences function iterates at most candidate_count² times
• add_pairs function iterates at most candidate_count² times, handles both cases properly
• sort_pairs function uses a sorting algorithm that will iterate on the order of candidate_count² times, regardless of whether elements are sorted (for example, selection sort)
• lock_pairs function uses at least one helper function
• print_winner function iterates at most candidate_count² times

Evidence of a 2-point Submission

• vote function does not short-circuit
• record_preferences function uses a conditional to check if a preference should be updated or not (iterates candidate_count² times)
• add_pairs function uses unnecessary variables, uses a conditional to check if a preference should be updated or not (iterates candidate_count² times)
• sort_pairs function may perform a swap by exchanging the elements of a pair item (as opposed to simply swapping the pair item itself), may use a sorting algorithm worse than candidate_count² iterations
• lock_pairs function uses no helper functions (may be lengthy with lots of repeated code), unnecessary variables, unnecessary conditionals, or helper functions that do not short circuit
• print_winner function does not short-circuit (may use a counter variable), uses unnecessary conditional statements

Evidence of a 1-point Submission

• vote function does not use the strcmp function
• record_preferences iterates more than candidate_count² times
• add_pairs function includes an empty else statement for the case of a tie, or doesn’t handle all of the cases
• sort_pairs function does not make use of the pair_count variable, uses an inefficient sorting method (for example, exhaustive sort)
• lock_pairs function uses a method that is extremely confusing and hard to understand
• print_winner function uses a method that does not reference the locked array

Example Implementations (Worse vs. Better)

vote Function

Worse Implementation

The example below will not short-circuit

int matches = 0;
for (int i = 0; i < candidate_count; i++)
{
    if (strcmp(name, candidates[i]) == 0)
    {
        ranks[rank] = i;
        matches++;
    }
}

if (matches > 0)
{
    return true;
}
else
{
    return false;
}

Better Implementation

The example below will short-circuit

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

record_preferences Function

Worse Implementation

The example below iterates unnecessarily many times (also forcing the need for an unnecessary conditional statement)

for (int i = 0; i < candidate_count; i++)
{
    for (int j = 0; j < candidate_count; j++)
    {
        if (i < j)
        {
            preferences[ranks[i]][ranks[j]]++;
        }
    }
}

Better Implementation

The example below chooses a better starting index for the innermost for loop, eliminating extra iterations

for (int i = 0; i < candidate_count; i++)
{
    for (int j = i + 1; j < candidate_count; j++)
    {
        preferences[ranks[i]][ranks[j]]++;
    }
}

add_pairs Function

Worse Implementation

Though the example below includes one fewer conditional statement, it will unnecessarily iterate over each pair of candidates twice

for (int i = 0; i < candidate_count; i++)
{
    for (int j = 0; j < candidate_count; j++)
    {
        if (preferences[i][j] > preferences[j][i])
        {
            pairs[pair_count].winner = i;
            pairs[pair_count].loser = j;
            pair_count++;
        }
    }
}

Better Implementation

The example below chooses a better starting index for the innermost for loop, eliminating the need to iterate over the entire 2D array

for (int i = 0; i < candidate_count; i++)
{
    for (int j = i + 1; j < candidate_count; j++)
    {
        if (preferences[i][j] > preferences[j][i])
        {
            pairs[pair_count].winner = i;
            pairs[pair_count].loser = j;
            pair_count++;
        }
        else if (preferences[j][i] > preferences[i][j])
        {
            pairs[pair_count].winner = j;
            pairs[pair_count].loser = i;
            pair_count++;
        }
    }
}

sort_pairs Function

Worse Implementation

This example is not only difficult to read due to line length, but it also unnecessarily swaps the pair values instead of the pairs themselves (adds unnecessary steps). Additionally, the algorithm may not be the most efficient choice (lots of swapping and computation required for each iteration through the algorithm)

bool swapped = false;
for (int i = 0; i < pair_count; i++)
{
    swapped = false;
    for (int j = 0; j < pair_count - i - 1; j++)
    {
        if (preferences[pairs[j].winner][pairs[j].loser] - preferences[pairs[j].loser][pairs[j].winner] < preferences[pairs[j + 1].winner][pairs[j + 1].loser] - preferences[pairs[j + 1].loser][pairs[j + 1].winner])
        {
            int temp_winner = pairs[j].winner;
            int temp_loser = pairs[j].loser;
            pairs[j].winner = pairs[j + 1].winner;
            pairs[j].loser = pairs[j + 1].loser;
            pairs[j + 1].winner = temp_winner;
            pairs[j + 1].loser = temp_loser;
            swapped = true;
        }
    }
    if (swapped == false)
    {
        break;
    }
}

Better Implementation

This example is much easier to read and swaps each entire pair (not just the inner values). Additionally, the algorithm performs fewer swaps for each iteration through, making it more efficient

for (int i = 0; i < pair_count - 1; i++)
{
    int max = i;
    int max_support = preferences[pairs[max].winner][pairs[max].loser];

    for (int j = i + 1; j < pair_count; j++)
    {
        int support = preferences[pairs[j].winner][pairs[j].loser];
        if (support > max_support)
        {
            max = j;
            max_support = support;
        }
    }

    pair_temp = pairs[i];
    pairs[i] = pairs[max];
    pairs[max] = temp;
}

lock_pairs Function

Worse Implementation

The example below is from a check_cycle helper function. It includes an unnecessary else statement, and two nested if statements that should be combined using a && operator

if (loser == first_winner)
{ 
    return true;
}
else
{
    for (int i = 0; i < pair_count; i++)
    {
        if (pairs[i].winner == true)
        {
            if (check_cycle(pairs[i].loser, first_winner) && locked[pairs[i].winner][pairs[i].loser])
            {
                return true;
            }
        }
    }
    return false;
}

Better Implementation

This example is also from a check_cycle helper function. No unnecessary if or else statements, and makes use of the visited array to simplify computation

visited[src] = true;

if  (locked[src][dst])
{
    return true;
}

for (int i = 0; i < candidate_count; i++)
{
    if (locked[src][i] && !visited[i] && check_cycle(i, dst, visited))
    {
        return true;
    }
}
return false;

print_winner Function

Worse Implementation

This example will not short-circuit

for (int i = 0; i < candidate_count; i++)
{
    int count = 0;
    for (int j = 0; j < candidate_count; j++)
    {
        if (locked[j][i])
        {
            break;
        }
        count++;
    }

    if (count == candidate_count)
    {
        printf("%s\n", candidates[i]);
    }
}

Better Implementation

This example includes short-circuiting

for (int i = 0; i < candidate_count; i++)
{
    bool winner = true;
    for (int j = 0; j < candidate_count; j++)
    {
        if (locked[j][i])
        {
            winner = false;
            break;
        }
    }

    if (winner)
    {
        printf("%s\n", candidates[i]);
        break;
    }
}