USING INDUCTION TO DESIGN ALGORITHMS

ARTICLES USING INDUCTION TO DESIGN ALGORITHMS An analogy between proving mathematical theorems and designing computer algorithms provides an elegant methodology for designing algorithms, explaining their behavior, and understanding their key ideas. UDI MANBER This article presents a methodology, based on mathe- matical induction, for approaching the design and the teaching of combinatorial algorithms. While this meth- odology does not cover all possible ways of designing algorithms it does cover many known techniques. It also provides an elegant intuitive framework for

ex- plaining the design of algorithms in more depth. The heart of the methodology lies in an analogy between the intellectual process of proving mathematical theo- rems and that of designing combinatorial algorithms. We claim that although these two processes serve dif- ferent purposes and achieve different types of results, they are more similar than it seems. This claim is es- tablished here by a series of examples of algorithms, each developed and explained by the use of the meth- odology. We believe that students can get more motiva- tion, greater depth, and better understanding of algo- rithms by this methodology. Mathematical induction is a very powerful proof technique. It usually works as follows. Let T be a theo- rem that we want to prove. Suppose that 7’ includes a parameter n whose value can be any natural number. Instead of proving directly that T holds for all values of This research was supported in part by an NSF grant MCS-8303134. and an NSF Presidential Young Investigator Award [grant DCR-8451397). with match- ing funds from Tektronix, Digital Equipment Corporation, and Hewlett Packard. 01988 ACM OOOl-0782/88/1100-1300 $1.50 n we prove that (1) T holds for n = 1, and (2) T holds for any n > 1 provided that T holds for n - 1. The first part is usually very simple to prove. Proving the second part is easier in many cases than proving the theorem di- rectly since we can use the assumption that T holds for n - 1. (In some sense we get this assumption for free.) In other words, it is enough to reduce the theorem to one with a smaller value of n, rather than proving it from scratch. We concentrate on this reduction. The same principle holds for algorithms. Induction allows one to concentrate on extending solutions of smaller subproblems to those of larger problems. One starts with an arbitrary instance of the problem at hand, and tries to solve it by using the assumption that the same problem but with smaller size has already been solved. For example, given a sequence of n > 1 numbers to sort (it is trivial to sort one number), we can assume that we already know how to sort n - 1 numbers. Then we can either sort the first n - 1 num- bers and insert the nth number in its correct position (which leads to...

Website: www.akira.ruc.dk | Filesize: -
No of Page(s): 14
Download USING INDUCTION TO DESIGN ALGORITHMS.pdf