Induction as a tool for conceptual coherence in computer science
Irene Polycarpou · 2008
Induction is central to many areas of computer science (CS) such as data structures, theory of computation, programming languages, program correctness/verification, and program efficiency. In this paper, I discuss the role of induction in the current CS curriculum and its applications in some of the above areas. I also shed some light on "hidden" applications of structural induction, and I demonstrate how induction can be used as a tool for conceptual coherence in CS. Proofs by induction are currently taught independently of their CS applications and as a "recipe" to be followed, without explaining the role of each ingredient. Moreover, there is no unified framework for induction throughout the CS curriculum, which I argue that is necessary for students to gain conceptual understanding.