Recursion is a programming technique in which a method (function) calls itself. It is one of the most interesting and surprisingly effective techniques in programming. In this lab we examine numerous examples to show what it is and how it works.
At the end of this lab, you need to submit a word document including some text answers and screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).
To execute an applet in Internet Explorer, perform the following steps.
(1.) Click Start > Windows System -> Command Prompt
(2.) Use command "cd" to move into the directory where you run the applet, such as cd C:\COSC3331\Chap06\Towers
(3.) Open the applet under typing "appletviewer Towers.html".
(4.) Enter 3 in Number and click New to create a new game with 3 disks for Figure 1, the computer will randomly initialize some color for each disk.
Fig. 1 Initial State for a 3-disk Hanoi Tower see image.
(5.) Click Step to observe the process (steps) you need to move all 3 disks from post A to C, you have Figure 2 after you finish. Q1: How many moves you need for 3 disks?
Fig. 2 Final State for a 3-disk Hanoi Tower see image.
(6.) Enter 4 in Number and click New to create a new game with 4 disks. This time use the mouse to drag the disk to move from one post to another. Remember only one disk can be moved at a time, and no disk can be placed on a disk that's smaller than itself. Could you find the solution of 4 disks of Hanoi Tower (Figure 3)? Q2: How many moves you need for 4 disks?
Fig. 3 Final State for a 4-disk Hanoi Tower see image.
(7.) Go to the link of http://haubergs.com/hanoi , continuing our lab here. Figure 4 is with 10 disks. Q3: How many moves you need for 5, 7, 10 disks?
(8.) Q4: Based on the data you've got, what do you guess for the algorithm order (in big O notation) of the recursion algorithm of Hanoi Tower?
Fig. 4 Hanoi Tower under Haubergs see image.
(1.) Under Command Prompt, change the directory by "cd C:\COSC3331\Chap06MergeSort".
(2.) Open the applet by "appletviewer MergeSort.html", see Figure 5.
Fig. 5 Initial State for 10 Bars of MergeSort see image.
(3.) Click Run to execute the merge sorting algorithm, we have Figure 6 after it finishes. Q5: What are the meanings of the blue arrow and the red arrows corresponding to the algorithm? Q6: After it stops, what are the numbers of copies and comparisons?(Your answers may be different with mine because of the different initial values)
Fig. 6 Final State for 10 Bars of MergeSort see image.
(4.) Click Size to toggle it to 100 bars, then press Run to execute the merge sorting algorithm, we have Figure 7 after it stops. Q7: after it stops, what are the numbers of copies and comparisons?
Fig. 7 Final State for 100 Bars of MergeSort see image.
(5.) If you want to trace the steps, you could use Draw to stop the running process, and then click Step to execute one step of sorting process.
(6.) Q8: List a table to compare your results of mergesort (both 10 bars and 100 bars) with the simple sorting algorithms (selecting sort and insertion sort in Lab 2), which one is faster? Assume one swap is equal to 3 copies and one copy is one comparison.
Q1: How many moves you need for 3 disks?
Q2: How many moves you need for 4 disks?
Q3: How many moves you need for 5, 7, 10 disks?
Q4: Based on the data you've got, what do you guess for the algorithm order (in big O notation) of the recursion algorithm of Hanoi Tower?
Q5: What are the meanings of the blue arrow and the red arrows corresponding to the algorithm?
Q6: After it stops, what are the numbers of copies and comparisons?
Q7: after it stops, what are the numbers of copies and comparisons?
Q8: List a table to compare your results (both 10 bars and 100 bars) with the simple sorting algorithms (selecting sort, insertion sort in lab 2), which one is faster? Assume one swap is equal to 3 copies.
Submit the screenshots for Figures 1, 2, 3, 6, 7 (totally 5 figures) through Blackboard. (Don't forget to include your name in the program). (At the end of this lab, you need to submit a word document including some screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs- >Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).