Correct vs. Incorrect Algorithms

Comparison of correct and incorrect algorithms

We say that an algorithm is correct when it translates every input instance into the correct output. An algorithm is incorrect when there is at least one input instance for which the algorithm gives an incorrect output.

Consider the $Change$ algorithm from the previous lesson.

---

 $Change(money, c, d)$:
 r $\leftarrow$ $money$
 for $k$ from $1$ to $d$:
       $i_{k}\leftarrow \lfloor{\frac{r}{c_{k}}}\rfloor$
       $r\leftarrow r - c_{k}\cdot i_{k}$
return $(i_{1}$ $+$ $i_{2}$ $+$ $\ldots$ $+$ $i_{d})$

---

$Change$ is an incorrect algorithm! Suppose you were changing 40 cents into coins with denominations of $c_{1} = 25$, $c_{2} = 20$, $c_{3} = 10$ ...