# Module 2 - Example: Using Proofs in Algorithms

CSCI304: Analysis and Design of Algorithms<br>
Nile University<br>
Ammar Sherif (email-ID: ASherif)<br>

## Problem Statement

Prove that the following algorithm is correct:


```python
def maxVal(A):
    """
    The Algorithm returns the maximum value in the list
    
    Input constraints: A is not empty
    """
    maxV = A[0]
    for v in A:
        if maxV < v:
            maxV = v
    return maxV
```


```python
maxVal([1,2,3,40,5,6])
```




    40



## Proof

We first try to try to formulate a hypothesis to help us in proving the correctness. It is as follows:

$$H(i): \text{ After the completion of the }i^{th} \text{ iteration,}$$
$$\boxed{\texttt{maxV} = \max(A[0],A[1],\cdots,A[i-1])}$$
Which is a compact representation of:
\begin{equation}
    \texttt{maxV} \in \{ A[0],A[1],\cdots,A[i-1]\}\\
    \land ( \texttt{maxV} \geq A[0] \land \texttt{maxV} \geq A[1] \land \cdots \land \texttt{maxV} \geq A[i-1] )
\end{equation}
To prove using Induction, we have two steps we have to show that it holds:
<ol>
    <li>Base Case</li>
    <li>Inductive Step</li>
</ol>

### Base case

After the completion of the first iteration, we know that $\texttt{maxV} = \max(A[0]) = A[0]$ because of the **initialization** at the first line before the loop. Therefore, we showed that $\boxed{H(1)}$ holds.

### Inductive step

We want to show that $$H(k) \implies H(k+1)$$
Therefore, assuming $H(k)$ is True:<br>
$$H(k) \implies \texttt{maxV}\rvert_k = \max(A[0],A[1],\cdots,A[k-1])$$
For the next iteration $\texttt{v} = A[k]$; then, we have a condition as follows
\begin{align*}
H(k) &\implies\\
\texttt{maxV}\rvert_{k+1} &=
\begin{cases}
\texttt{v} = A[k], \qquad \texttt{maxV}\rvert_{k} < A[k]\\
\texttt{maxV}\rvert_{k}, \qquad \text{otherwise}
\end{cases}\\
&= \max(\texttt{maxV}\rvert_{k},A[k])\\
&= \max(\underbrace{\max(A[0],A[1],\cdots,A[k-1])}_{H(k)},A[k])\\
&= \max(A[0],A[1],\cdots,A[k])
\end{align*}
Therefore, after the end of this iteration the variable
$$\underbrace{\texttt{maxV} = \max(A[0],A[1],\cdots,A[k])}_{H(k+1)}$$
$$\boxed{H(k) \implies H(k+1)}$$

### Termination

Now, using the induction proof above: we know that after the last iteration, $m^{th}$ iteration, $H(m)$ holds. Therefore, $$\texttt{maxV} = \max(A[0],\cdots,A[m-1])$$
The remaining is that our algorithm terminates after the end of the loop, returning the maximum value, so the algorithm is *correct*.

acd911664dc7493afe0fde36bb9741e428578935
ipynb
Jupyter Notebook
Module 02: Introduction to Theoretical Analysis/Module 02: Example on Correctness Proofs.ipynb
ammarSherif/Analysis-and-Design-of-Algorithms-Tutorials
c45fa87ea20bc35000efb2420e58ed486196df14
MIT
Module 02: Introduction to Theoretical Analysis/Module 02: Example on Correctness Proofs.ipynb
ammarSherif/Analysis-and-Design-of-Algorithms-Tutorials
c45fa87ea20bc35000efb2420e58ed486196df14
MIT
Module 02: Introduction to Theoretical Analysis/Module 02: Example on Correctness Proofs.ipynb
ammarSherif/Analysis-and-Design-of-Algorithms-Tutorials
c45fa87ea20bc35000efb2420e58ed486196df14
MIT
Qwen/Qwen-72B
1. YES
2. YES