A method to construct counterexamples for greedy algorithms
Maddirla Jagadish, Sridhar R. Iyer · 2012
Problem solving is the focus of any algorithm design course. Being able to construct counterexamples is a critical part of the problem solving process. We address the following question: Is there a teachable approach to construct counterexamples? We present a technique, called the Anchor Method, that could prove useful in constructing counterexamples for greedy algorithms. The basic idea of the method is to get insight about the structure of a counterexample by weakening the greedy algorithm. We show the applicability of the method by constructing counterexamples for some classic problems in graph theory. We also investigate the teachability of the technique through experiments.