ITEC 2610 Assignment Four

1. The Tower of Hanoi
(a) Compile and run the JSS implementation (on page 598 - 600) of the Tower of Hanoi.
You should have three pegs (from left to right peg0, peg1, and peg2). Disks however are (from the smallest to the largest) disk1, disk2, ..., diskn. All the desks are stacked on peg0 initially. It is asked to move all disks from peg0 to peg2. The output for the program with 3 disks is:

Move one disk from 0 to 2
Move one disk from 0 to 1
Move one disk from 2 to 1
Move one disk from 0 to 2
Move one disk from 1 to 0
Move one disk from 1 to 2
Move one disk from 0 to 2

(b) Revise your implementation to include stepwise states of the tower, like the following. Initially:

peg0: 3 2 1
peg1: 0 0 0
peg2: 0 0 0
Step 1: Move disk1 from peg0 to peg2 resulting
peg0: 3 2 0
peg1: 0 0 0
peg2: 1 0 0
Step 2: Move disk2 from peg0 to peg1 resulting
peg0: 3 0 0
peg1: 2 0 0
peg2: 1 0 0
Step 3: Move disk1 from peg2 to peg1 resulting
peg0: 3 0 0
peg1: 2 1 0
peg2: 0 0 0
Step 4: Move disk3 from peg0 to peg2 resulting
peg0: 0 0 0
peg1: 2 1 0
peg2: 3 0 0
Step 5: Move disk1 from peg1 to peg0 resulting
peg0: 1 0 0
peg1: 2 0 0
peg2: 3 0 0
Step 6: Move disk2 from peg1 to peg2 resulting
peg0: 1 0 0
peg1: 0 0 0
peg2: 3 2 0
Step 7: Move disk1 from peg0 to peg2 resulting
peg0: 0 0 0
peg1: 0 0 0
peg2: 3 2 1

(c) We have 10 disks, i.e., Initially:

peg0: 10 9 8 7 6 5 4 3 2 1
peg1: 0 0 0 0 0 0 0 0 0 0
peg2: 0 0 0 0 0 0 0 0 0 0
Step 1: Move disk1 from peg0 to peg1 resulting
peg0: 10 9 8 7 6 5 4 3 2 0
peg1: 1 0 0 0 0 0 0 0 0 0
peg2: 0 0 0 0 0 0 0 0 0 0
... ... ...
Show the states resulted from Step 500 to Step 504.
2. Insertion/Selection/Merge/Quick Sorts In total n integers ranging from 0 to n − 1 are stored randomly in A, an array of size n. You are supposed to implement the following four candidate sorting algorithms to sort A: Insertion Sort, Bubble Sort, Selection Sort, and Quick Sort (At each recursion, you will have to choose the first element in the array as the pivot element). Note that, important, you have to work directly on the given starter code.Download the starter code from the course web site. Read the starter code and make sure you understand how it works before attempting to modify it. Design modifications to the starter code for the methods that described in the Introduction section. Update the starter code with your modifications. Run the code and your simulation. Submit 1) a printout of
any file that you modified or added to the starter code; 2) a printout of the output from yoursimulation. Note that running Solver.java with your implementation, an example output is Initially, the array is:
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
After randomization, the array becomes:
91 54 53 47 86 2 51 99 52 31
60 15 59 43 56 78 32 10 12 70
33 34 11 96 92 66 4 88 41 22
85 18 23 57 24 83 35 44 5 68
48 79 46 71 42 82 25 29 30 21
27 94 20 6 84 73 77 81 28 38
75 89 39 36 45 62 65 1 49 87
50 67 90 40 55 93 64 19 0 61
37 8 69 98 3 16 9 58 97 63
80 95 7 74 26 72 14 76 13 17
The array is now sorted:
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
2