Description
0. Create package prog07 and add Heap.java.
1. In Heap, go over all the methods up to and including offer. Make
sure you understand them. Implement poll(). It uses ITERATION.
For the final loop, what’s the condition on the while?
The item at index is greater than one of its children.
How do you say this in Java:
(The item at) index is greater than its left child or
index is greater than its right child
More specifically
index has a left child and is greater than that child
or
index has a right child and is greater than that child
Once you have this condition, then you need to do the inside of the loop:
swap index with the smaller child
More specifically
if right child is less than left child
then swap index with right
else swap index with left
Can you get the logic right? Remember, the parent might not HAVE a
right child. Who wins then? Make sure the if condition handles this case.
DUE Wednesday March 6 at 11am
8. Copy your WordStep.java from prog06 to prog07 and change the
package of the copy to prog07 at the top.
9. Add code to solve so it displays a message about how many times it
polls the queue. (Poll is expensive because you have the check the
entire dictionary for neighbors.) You should get 481 for “snow” to
“rain”.
10. Add a method
static int numSteps (int[] parents, int index)
that takes the parents array and an index as input and returns the
number of steps back to the start word index (which will have -1).
For example, if parents is
[0[ [1] [2] [3] [4] [5] [6] [7]
-1 -1 1 2 1 4 5 4
then numSteps(parents, 6) returns 3 because
parents[6] == 5
parents[5] == 4
parents[4] == 1
parents[1] == -1
so it takes 3 steps, 5, 4, 1, to get to a -1.
Add a message to solve that tells you how far the target is from
the start (when you have found the path).
11. Add a static method numDifferent that tells you the number of
letters that are different in two words. For example,
numDifferent(“snow”, “slot”) == 2
Test it.
12. Add a class IndexComparator (INSIDE the WordStep class!) that
implements Comparator<Integer>.
a. Its constructor IndexComparator(parents, target) should take
the parents array and the target word as arguments and store
them inside IndexComparator.
b. The method sumNums(index) returns the number of steps from
the index to the start index PLUS the number of differences
between the word at that index and the target word.
c. The method compare(index1, index2) (required by the Comparator
interface) should return < 0 if sumNums(index1) is smaller than
sumNums(index2), = 0 if they have the same value, and > 0
otherwise.
13. In solve, switch to using a PriorityQueue<Node> using
IndexComparator for the Queue. How many words does it dequeue
now? (Should be 117.)
14. Now switch to using your Heap using your Comparator. It should
run the same. Switch back to PriorityQueue for the next part.
13. Unfortunately, you will also notice that the solution for “snow”
to “rain” is LONGER than before. Here is how to fix this.
a. Implement the remove method in Heap.
b. When WordStep solve dequeues the current word index and looks
at all elements of the dictionary for neighbors, instead of
just words with parents[index] == -1, it it should also
consider words that have
numSteps(parents, currentIndex) + 1 < numSteps(parents, index)
If parents[index] != -1, it should remove it from the queue
before adding it to the queue. (Yes, REMOVE IT and then add it
as usual.)
solve() should now find the same length solution for snow to rain
but dequeue far fewer words than the prog06 solve(). (Should be 74.)
Switch back to Heap and make sure it still works right.
IN LAB on Wednesday March 6:
BST.java will be another implementation of a Java Map. The Node class
has data, left, and right. In a binary search tree, left is less and
right is greater.
The toString method prints tree sideways. You have to turn your head
to the left to get the traditional view. So for instance, when it
prints
n 4
l 2
c 5
b 0
a 3
it is really the tree
b
0
a l
3 2
c n
5 4
14. Download BST.java. Implement the private find method using the
notes. Methods in BST should use RECURSION not iteration.
15. Implement the private add method using the notes. Remember that
you need to say Node<K,V> instead of Node so it works generically.
Make sure you understand what every line does. The TA can do some
examples on the board. Now, implement the public put method using
add. What do you do with the value add returns?
Test the program. The output should be as in tree-output.txt, only
the removes won’t happen.
16. Delete the first two lines from the public remove method.
Implement the private remove method based on the notes. It will
call removeRoot.
17. Implement removeRoot. It will call getMinimum and removeMinimum.
The node returned by getMinimum becomes the root.
18. Implement getMinimum and removeMinimum.
