I've seen references to cut-and-paste proofs in certain texts on algorithms analysis and design. It is often mentioned within the context of Dynamic Programming when proving optimal substructure for an optimization problem (See Chapter 15.3 CLRS). It also shows up on graphs manipulation.

What is the main idea of such proofs? How do I go about using them to prove the correctness of an algorithm or the convenience of a particular approach?

Edit
Report