Article: Reversing: An Essential Heuristic in Program and Proof Design
Reversing is the notion of thinking, or working in reverse. Computer science textbooks and tutors recognize it primarily in the form of recursion. However, recursion is only one form of reversing. Reversing appears in the computer science curriculum in many other forms, at various intellectual levels and in a variety of fundamental courses.
Reversing is encapsulated in mathematical inversion (of functions, or representations); it is enclosed in reverse transformation; it appears in the topological reverse of ordered structures (such as sequences and directed graphs); it is embodied in the notion of “complement”; and it is the core of backward reasoning and logical reverse (contra-positive).
These forms of reversing appear in fundamental courses throughout the curriculum, including Discrete Mathematics, CS1, CS2, Introduction to Algorithms, Computation Theory, Formal Languages Theory, Artificial Intelligence, and more. In some of the courses, the notions indicated above are employed in program and algorithm design; and in other courses, they are employed in the design of proofs.
The wide, thorough, and diverse appearances of reversing, place it in the domain of computer science as both a fundamental idea and an essential problem solving means. Yet, the notion of reversing is not explicitly underlined as such during the CS studies. The primary objective of the paper is to demonstrate the latter, and illuminate the essential role of reversing in the CS curriculum, primarily in program and proof design.
In the paper, we describe each of the above reversing forms, and demonstrate its appearances with actual illustrations. The illustrations are divided into those that involve program or algorithm design, in the courses of CS1, CS2, and Introduction to Algorithms; and those that involve proof design, in the courses of Computation Theory and Formal Languages Theory.
Although fundamental, reversing is unintuitive to many. This is already partly demonstrated in studies of recursion. In our presentation, we briefly indicate our primary experience with student difficulties: in inverting sequences, turning to the complement graph, employing reductions in proofs, employing contra-positive arguments, and inverting set-closure properties. Yet, our primary focus is on the demonstration of reversing as a fundamental idea and a problem solving means in computer science. It is our hope that textbooks and tutors will repeatedly underline the latter and explicitly demonstrate to students the relevant relatedness between the various forms of reversing.
Author 1: David Ginat [email protected]
Author 2: Michal Armoni [email protected]
Article Link:
http://portal.acm.org/citation.cfm?id=1121488&coll=portal&dl=ACM&CFID=9122936&CFTOKEN=32438184