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!