3
$\begingroup$

I'm working through a few chapters on algorithms from the Discrete Math text by Rosen.

In the solutions manual there is an algorithm (specified in pseudocode) for finding the mode within a list of non-decreasing integers.

Here is the algorithm:

procedure find a mode(a_1, a_2, ... , a_n : non-decreasing integers)
modecount = 0
i = 1
while i <= n 
    value = a_i
    count = 1
    while i <= n and a_i == value
        count = count + 1
        i = i + 1
    if count > modcount then
        modecount = count
        mode = value
return mode

Now, I immediately see a problem with this algorithm. For instance, take the list $<1,2,2,2,4,4,4>$ we see that the following steps are followed, counting the element $1$ twice when it only appears in our list once.

Steps below begin upon first entry of the body of the while loop:

Step 1. Assign $a_1=1$ to $value$.

Step 2. Assign $1$ to $count$

Step 3. Check that $i=1 \leq 7$ and that $a_1=1$ equals $1=value$.

Step 4. Increase the value of $count$ by $1$ so that $count := 2$.

But we only have $1$ appearing once in our list and we have counted it twice.

Is my interpretation of this algorithm incorrect? To me $count$ should first be set to $0$.

$\endgroup$
3
$\begingroup$

Yes, you are right. The pseudocode is clumsy, poorly constructed, and confusing. At the end of the outer loop, modecount holds the number of times that value appears in the array, plus one. That's weird and not what you'd expect from the variable name: from the variable name, we'd expect it to hold the number of times value appears (without the plus one).

That said, the algorithm still returns the correct answer: it does indeed return a mode, as claimed. For example, with your example input, it correctly returns 2.

(Why? Because the exact value of modecount isn't returned. It's one too high for every value, so the mode will indeed have the largest value of modecount.)

So while the pseudocode is confusing and poorly constructed, it happens to return the right answer -- i.e., it happens to be a correct algorithm for the "find a mode" problem. But it's still ugly. Yuck. I agree with you that they should have initialized the count to 0, not 1; then the algorithm would be both correct and easier to understand.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.