11
$\begingroup$

In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an algorithm already known to be correct, is correct. We've never been asked to show that an algorithm isn't correct.

Are there any classic examples of algorithms that look correct, but aren't? I am looking for cases where the Initialization-Maintenance-Termination approach catches something that first-glance intuition doesn't.

$\endgroup$
  • 5
    $\begingroup$ Possibly of interest: cs.stackexchange.com/q/29475/755 $\endgroup$ – D.W. Mar 29 '18 at 19:53
  • 5
    $\begingroup$ Upvoting because I think that this is a very important pedagogical question. It is slightly out of scope for cstheory, but I don't know a better platform for it, and there are many algorithms instructors in the cstheory community. Most algorithm-design courses expose students only to correct, existing algorithms and to problems that are easily solvable using known techniques. This reinforces the impression, so attractive to students, that one can safely trust one's intuitive feeling that a seemingly plausible algorithm is right. A good algorithm-design course should do the opposite! $\endgroup$ – Neal Young Mar 31 '18 at 2:14
  • 3
    $\begingroup$ I would love to have a collection like this. $\endgroup$ – Chandra Chekuri Mar 31 '18 at 11:28
18
$\begingroup$

2D local maximum

input: 2-dimensional $n \times n$ array $A$

output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value.

(The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.) So, for example, if $A$ is

$$\begin{array}{cccc} 0&1&3&\mathbf{4}\\ \mathbf{3}&2&\mathbf{3}&1\\ 2&\mathbf{5}&0&1\\ \mathbf{4}&0&1&\mathbf{3}\end{array}$$

then each bolded cell is a local maximum. Every non-empty array has at least one local maximum.

Algorithm. There is an $O(n^2)$-time algorithm: just check each cell. Here's an idea for a faster, recursive algorithm.

Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row. First check each cell in $X$ to see if the cell is a local maximum in $A$. If so, return such a cell. Otherwise, let $(i, j)$ be a cell in $X$ with maximum value. Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.

Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way. The neighboring cell $(i', j')$ with larger value must be in one of those quadrants. Call that quadrant $A'$.

Lemma. Quadrant $A'$ contains a local maximum of $A$.

Proof. Consider starting at the cell $(i', j')$. If it is not a local maximum, move to a neighbor with a larger value. This can be repeated until arriving at a cell that is a local maximum. That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$. This proves the lemma. $\diamond$

The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.

The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.

Thus, we have proven the following theorem:

Theorem. There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.

Or have we?

$\endgroup$
  • $\begingroup$ At first reading, the only mistake I spotted was the recurrence solution. Is that the only mistake? $\endgroup$ – Radu GRIGore Mar 31 '18 at 8:08
  • 1
    $\begingroup$ The recurrence is correct. The algorithm is not! $\endgroup$ – Neal Young Mar 31 '18 at 11:08
  • $\begingroup$ Ah, yes, I made a dumb mistake with the recurrence. I see the problem: the maximum you prove exists is not (necessarily) what you find. And what you find ignores the X. $\endgroup$ – Radu GRIGore Mar 31 '18 at 11:19
  • 2
    $\begingroup$ Here's an example: $$\begin{pmatrix}2&1&4&3&3&0&0\\1&0&1&2&3&0&0\\0&{\color{red}1}&0&2&3&0&0\\2&2&2&2&2&2&2\\3&3&3&2&3&3&3\\0&0&3&2&3&0&0\\0&0&3&2&3&0&0\end{pmatrix}$$ $\endgroup$ – Radu GRIGore Mar 31 '18 at 11:42
  • 1
    $\begingroup$ @Marin, what is missing is a proof that a local maximum of $A'$ is also a local maximum of $A$, because it's not true. (I somehow like my initial wording, but it is not precise, and it is not clear. But, it may aid intuition.) $\endgroup$ – Radu GRIGore Apr 4 '18 at 5:11

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.