0
$\begingroup$

New to proofs (in the context of analysis of algorithms).

I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + termination).

I'm trying to understand how The Job Sequencing Problem is correct but can only find proofs for its optimality. How can we be sure this algorithm is correct?

EDIT: I have found an excellent resource that uses a proof of optimality to show (I think) partial correctness as well. It is here but for the life of me I cannot understand it. A layman's explanation would be amazing!

$\endgroup$
3
  • 1
    $\begingroup$ Termination is usually obvious for greedy algorithms. $\endgroup$ – Yuval Filmus May 20 at 22:17
  • 1
    $\begingroup$ And optimality is the definition of correctness in optimization-type problems $\endgroup$ – nir shahar May 20 at 22:27
  • $\begingroup$ Maybe edit your post to include a reference to your resource so we can have a look at it? $\endgroup$ – ShyPerson May 20 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.