3
$\begingroup$

So I have this algorithm that outputs the largest value of an array:

  • Input: $A[1,\dots,n]$, $n\geq 1$
  • Output: Largest value of an array
Maximum (A) m = A[1] i = 1 while i < n if A[i+1] > A[i] m = A[i+1] i = i+1 return m

I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ Simple: give a counter-example, i.e. an input for which the algorith computes the wrong thing. $\endgroup$ Commented Apr 15, 2018 at 19:29
  • $\begingroup$ @Evander, be careful with indentation when you reformat code. $\endgroup$ Commented Apr 16, 2018 at 10:18

2 Answers 2

Reset to default
4
$\begingroup$

Consider the input $100,0,1$.

As a follow-up, identify the bug, and correct the algorithm.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Hint: the code doesn’t do what it should do. Check the code literally as it is written, not as you think it should be written. It’s the kind of bug where you bang your head on the table and wonder how you could have ever missed it. $\endgroup$ Commented Apr 16, 2018 at 14:34
  • $\begingroup$ Don't forget that there are multiple solutions to a problem. As mentioned below you could rewrite the conditional, but an alternative is to strengthen the pre-condition to the code fragment: Insist the array is sorted, then the m will be assigned the maximum ;-) $\endgroup$ Commented May 4, 2018 at 13:10
-1
$\begingroup$

Two points which will prove the algorithm is wrong

  1. Array type starts with the zeroth element, in that case, A[0] will be eliminated even if it's the highest number. So, m should start with A[0], not A[1].
  2. The comparison of each element should be made with the maximum number element(m) and not with its previous element. So, it should be A[i+1] > m, not A[i+1] > A[i]
Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Your point 1 is besides the point. 0-based indexing is a choice. $\endgroup$ Commented Apr 18, 2018 at 6:40
  • $\begingroup$ Why should the comparison be made with the current maximum rather than with the previous element? $\endgroup$ Commented Apr 18, 2018 at 7:35

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.