I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same sentence!
From my best unconfirmed understanding, the optimal proof uses "greedy stay ahead" where I need to show that greedy algorithm constructs a solution set that is no worse than the optimal set
The correctness proof utilizes the swapping argument to show that any difference between output set A and optimal set OPT can be eliminated by swapping the items in the optimal set.
Can someone clarify if I must only use the "greedy stay ahead" proof method for the optimal proof and not the correctness proof? And must I use the swapping argument (with contradiction) to show that swapping items in the optimal set?
Greedy stay ahead: http://www.cs.cornell.edu/Courses/cs482/2007sp/ahead.pdf
Swapping: http://www.cs.oberlin.edu/~asharp/cs280/handouts/greedy_exchange.pdf (Note that author states that this proves correctness and ends with prove optimality)
Instance where swapping was used to prove optimality, greedy stay ahead used to prove correctness: http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/notes-5z-unit-5-filled-in.pdf