  Computational and complexity theory are core components of the computer
science curriculum, and in the vast majority of cases are taught using decision
problems as the main paradigm. For experienced practitioners, decision problems
are the best tool. But for undergraduates encountering the material for the
first time, we present evidence that non-decision problems (such as
optimization problems and search problems) are preferable. In addition, we
describe technical definitions and pedagogical strategies that have been used
successfully for teaching the theory course using non-decision problems as the
central concept.
