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 !


closed as primarily opinion-based by David Richerby, xskxzr, Thinh D. Nguyen, Evil, Apass.Jack Oct 26 '18 at 19:32

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – Apass.Jack 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$ – Apass.Jack 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