3
$\begingroup$

I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and proving their formulas I can do it, I have no problem understanding why it is correct. When I get a loop on the other hand, I cannot even get started. I have a hard time combining the Loop invariant (also finding it) and the proof.

For example the following is a complete mystery (i tried reading a few similar questions on SO, but I still don't get it)

function multiply(y, z)
    if z = 0 then return(0) else
    return(multiply(cy, ⌊z/c⌋) + y · (z mod c))

I understand that I am asking a lot, but is it possible for someone to try to explain it step by step ? I am learning the book on my own, this is not a homework and I am not trying to cheat on anything, I just do not understand it.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Try to formally state your induction hypothesis, what are you inducting over? what do you assume? what do you need to prove. After doing this, you will see that your problem reduces to showing $\forall c>0 : yz = cy\cdot\left\lfloor \frac{z}{c}\right\rfloor+y\cdot (z \mod c)$ $\endgroup$
    – Ariel
    Commented Nov 17, 2016 at 9:34
  • 2
    $\begingroup$ Your question seems too broad to answer. Proving algorithms correct is like proving anything else in mathematics: it requires skill and creativity and you can't just apply a recipe. I think you need an interactive setting (such as a tutor) rather than written answers on the internet to really help you. $\endgroup$
    – David Richerby
    Commented Nov 17, 2016 at 9:37
  • $\begingroup$ @Ariel how do I include the if else statement in the proof ? $\endgroup$
    – Martin Spasov
    Commented Nov 17, 2016 at 9:50
  • 3
    $\begingroup$ Jeff Erickson has some fantastic from-the-ground-up notes on proofs by induction here: jeffe.cs.illinois.edu/teaching/algorithms/notes/…. $\endgroup$
    – j_random_hacker
    Commented Nov 17, 2016 at 12:28

2 Answers 2

Reset to default
3
$\begingroup$

how do I include the if else statement in the proof?

In this example, the if statement describes the basic case and the else statement describes the inductive step.

Induction on $z$.

Basis: $z = 0$.

$$ \text{multiply}(y,z) = 0 = y \times 0. $$

Induction Hypothesis: Suppose that this algorithm is true when $0 < z < k$. Note that we use strong induction (wiki).

Inductive Step: $z = k$.

\begin{align} \forall c>0 : \text{multiply}(y,z) &= \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) \\ &= cy\cdot\left\lfloor \frac{z} {c}\right\rfloor+y\cdot (z \text{ mod } c) \\ &= yz. \end{align}

Improve this answer
$\endgroup$
2
$\begingroup$

Expanding on hengxin's succinct answer, this is my understanding of how each step is achieved.

We do the inductive step on $z = k$. This means that in the first invocation of $multiply(y, z)$, $z$ is in fact $k$.

$ \text{multiply}(y,z) = \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) $

The first term is $multiply(cy, \lfloor \frac{z}{c} \rfloor)$, in which $\lfloor \frac{z}{c} \rfloor$ is really $\lfloor \frac{k}{c} \rfloor$, and $\frac{k}{c} < k$. From our inductive assumption that $multiply(y, z) = yz$ for all $0 < z < k$ therefor follows that we can assume that $multiply(cy, \lfloor \frac{z}{c} \rfloor) = cy \cdot \lfloor \frac{z}{c} \rfloor$, and so we get:

$ = cy\cdot\left\lfloor \frac{z} {c}\right\rfloor+y\cdot (z \text{ mod } c) $

We can now break out $y$ from the terms:

$ =y \cdot \left(c\cdot\left\lfloor \frac{z} {c}\right\rfloor+ (z \text{ mod } c)\right) $

Lastly, because $c\cdot\left\lfloor \frac{z} {c}\right\rfloor$ removes the remainder of $\frac{z}{c}$ from $z$ and $z \text{ mod } c$ adds it back again, the expression in the parens can be re-written as $\left(c\cdot\left\lfloor \frac{z} {c}\right\rfloor+ (z \text{ mod } c)\right) = z$, which means we get:

$ =yz $

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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