Kang Sun, PhD

kangsun@coe.neu.edu

School of Engineering Technology

Northeastern University

Boston, MA 02115

**Abstract**

We as engineering and technology educators have been constantly seeking innovative and effective ways of transferring knowledge to technology students. In this paper I want to share my experience of using a simple Java applet in the classroom to convey several important concepts to students.

The Tower of Hanoi

Tower of Hanoi is a classical problem in computer science and mathematics. Almost all textbooks on advanced programming languages and computer algorithms use Tower of Hanoi as an example of recursive programming and algorithm complexity [1][2]. Several features of this problem make it interesting and attractive.

- It is fun as an educational game.
- It is seemingly complex yet has a very simple solution, ideal for demonstrating the power of recursive programming.
- The recursive solution is exponential and is used to convey the concept of complexity of algorithms.
- A group of practical problems, such as the travelling salesman’s problem and the shortest path problem, can be reduced to the problem of Hanoi of Tower. Finding tractable solution to solve these problems has been a challenging task for many years (the NP Complete problem).

According to the legend, once upon a time, there was a mountain, on top of which there was a temple, inside of which there was a monk who was doing nothing but predicting the end of the world. He has 64 golden plates of all different sizes and three silver poles. Initially all plates are stacked on the first pole (A), with the largest one at the bottom and the smallest one on the top. His goal is to move all the plates from the first pole (A) to the third (C), the second pole (B) is used temporarily to hold plates. Each day he moves only one plate from one pole to another; but at no time a larger plate can be placed on top of a smaller one. Plates have to be on one of the three poles at all time. He claimed when he finishes moving plates the world vanishes.

The recursive algorithm to solve this problem looks very simple.

Procedure Hanoi (No_Plates, Pole_From, Pole_To, Pole_Via) {

If (No_Plates > 0) {

Hanoi (No_Plates -1, Pole_From, Pole_Via, Pole_to);

Move one plate from Pole_From to Pole_to;

Hanoi (No_Plates -1, Pole_Via, Pole_to, Pole_From);

}

}

Explaining the recursive operation step by step of this simple algorithm and making it comprehensible to students is a challenge. I tried drawing pictures and tracing the stacks of recursion on blackboard. From the eyes of my audience I saw more confusion and puzzling. One day I was finally able to demonstrate in classroom a Java applet I wrote a couple of years ago when I first learned Java [2][3].

I run this applet for N=3, students counted the
number of moves while watching the actual action. By the time I tried
to move 6 plate, a student already figured out that it requires 64
moves because 2^{6}=64. As N getting larger, students got the
sense how the algorithm worked and why the number of moves doubled
when the number of plates increased by one.

While I got the students’ attention and interests, I ask them to calculate the number of days it needs for the monk to move all the plates if he followed this algorithm. And then converting the number of days to number of years and compare it with the age of civilization, the age of earth, and the age of universe. Discuss whether the monk’s prediction in the legend made sense. Students really learn to appreciate the meaning of exponential explosion and the tractability of algorithms.

I further explained the difference between optimal algorithm and practical close-to-optimal solution to real-world problems and stressed that our goal as engineers and technologists is to design and implement efficient, sub-optimal solutions to real world problems.

Further Thought

This experience reminded me of an incident I encountered at a classroom where the teacher had a difficult time explaining sorting algorithms to students, even though he tried with diagrams on blackboard, scattered papers on the table. Java is a sophisticated object oriented programming language and one can write an applet to implement a sorting algorithm class to demonstrate the operation of most of the sorting algorithms visually and dynamically. Applets can be written for tree-navigating algorithms as well as graph-navigating algorithms. Such applets make very effective tools for teaching engineering and technology. I would love to hear that such applets are available or interests and supports for developing such applets. As I said at the beginning of this article: A Java applet is worth a thousand words and pictures added together. Or did I say that?

[1] "C++, An Introduction to Computing",
2^{nd} Ed, Joel Adams, Sanford Leestma, and Larry Nyhoff, ISBN
0-13-744392-7, Prentice Hall, 1998.

[2] "Java How to Program with an Introduction to Visual J++", Deitel & Deitel, ISBN 0-13-632589-0, Prentice Hall, 1997.

[3] "Teach Yourself Java 1.1 In 21 Days With
CD-ROM", 2^{nd} Ed. Laura Lemay, ISBN:1-57-521142-4, SAMN,
1997.