The following guidelines are expected for all homework submissions:
all over the mapon *my* computer or in my editor. USE SPACES INSTEAD. You can set up almost every modern text editor to insert spaces whenever you press the TAB key, or you can simply pound the spacebar.
pair programmingwhich is part of the Extreme Programming software development method. Feel free to collaborate in your pairs as much as you want, doing the entire assignment together.
This problem set has two problems from chapter 11, one problem from chapter 9, and one problem from chapter 12. You will be working with tree traversals, heaps, and hashes for this assignment. Your task is to complete the following problems using the programs specified in each one. As always, when you are finished and ready to submit your work, do so in your repo. MAKE SURE YOUR CODE MODULES ALL COMPILE FROM THE COMMAND LINE! Here are the problems:
in–ordertraversal of a tree. It should display all the items in the proper order. Remember that
in–ordermeans you visit the left sub–tree, then the current node, then the right sub–tree.
PriorityQclass in the
PriorityQ.javaprogram [Listing 4.6] using a
heapinstead of an array. You should be able to use the
Heapclass in the
heap.javaprogram [Listing 12.1] without modification. Make it a descending queue [largest item is removed].
linear probe hash tablethat stores strings. You'll need a hash function that converts a string to an index number; see the section
Hashing Stringsin chapter 11. Assume the strings will be lowercase words, so 26 characters will suffice.
hash functionto implement a digit-folding approach in the hash function [as described in the
Hash Functionssection of chapter 11]. Your program should work for any array size and any key length. Use linear probing. Accessing a group of digits in a number may be easier than you think. Does it matter if the array size is not a multiple of 10?