2
$\begingroup$

I would like to know where I can find challenging exercises that ask to prove the correctness of an algorithm.

The invariant of most of the exercises I’ve found on the internet are quite easy (factorial, binomial coefficients...).

That’s why I was wondering if there exist a book or some online ressources where I can find challenging proof correctness’s exercises ?

Thank you !

$\endgroup$
  • $\begingroup$ Programming: The Derivation of Algorithms by Kaldewaij ;-) $\endgroup$ – Musa Al-hassy Oct 25 '18 at 19:32
  • $\begingroup$ @MusaAl-hassy Didn’t know that book :) If you have time can you provide an example of exercise in this book ? :-) $\endgroup$ – Thinking Oct 25 '18 at 23:11
  • $\begingroup$ Surprisingly, when I searched "proof" or "prove" in the search bar on the top left of this page, the questions returned by the search is roughly described by "most of the exercises I’ve found on the internet are quite easy". (Well, it is not surprising at all once I took a moment to think.) $\endgroup$ – John L. Oct 26 '18 at 0:47
  • $\begingroup$ Since you did not state your background, I will assume you are not very much into algorithms yet. You can read the most popular book Introduction to Algorithms by CLRS (four people here). There are plenty of exercises in that books that is much harder than the internet average. $\endgroup$ – John L. Oct 26 '18 at 19:31
  • 1
    $\begingroup$ @Thinking The text begins with a specification of the problem, then brings in formality when necessary, then derives code which is then correct by construction! E.g., include standard sorting algorithms as well as heap sort, classical loop problems, as well as 2-dimensional array probelms such as saddle sort ;-) $\endgroup$ – Musa Al-hassy Oct 28 '18 at 14:11