Due Date: November 28, 2018 [2018-11-28, Wednesday of week14]
The following guidelines are expected for all homework submissions:
- All homework must be typed. Homework which is not typed will be returned ungraded and will be
subject to the late homework guidelines as set out on the syllabus page. PLEASE DO NOT scribble
something on lined paper and rip it out of your spiral notebook — hanging chads went out
with the presidential election in 2000.
- I don't care too much about what font you use or how large your margins are; however, you might
want to check out a monospaced font for typing code, as it will be easy to see the indentations.
- Speaking of indenting, PLEASE DON'T USE TABS TO INDENT YOUR CODE. Tabs can often get interpreted
differently by different computers and applications, and could make code that is nicely formatted
on your computer look
all over the map on my computer or printer. 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.
- Work with a partner. I can't stress this enough; part of this policy is don't
split up the work – WORK TOGETHER on the assignment. This activity mimics
an industry code development model called
pair programming which 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.
- DO NOT share your work between groups. Doing so will count as plagiarism. If you wish to discuss
solutions with another group over coffee in the Lair, that's fine as long as it is kept at the
conceptual and you don't share your code between groups. Each group needs to turn in its
own version of the solutions.
- You only need to turn in one copy per group.
- Submit your homework through GitHub, in your repository, to which I must be a contributor or have
otherwise been allowed access. I cannot evaluate what I cannot see!
Problems for Assignment #4
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:
- Write a method that does an in–order traverse of a tree. It should display all the items
in the proper order. Remember that
in–order means you visit the left sub–tree,
then the current node, then the right sub–tree.
- Implement the PriorityQ class in the PriorityQ.java program (Listing 4.6) using a heap instead of an
array. You should be able to use the Heap class in the heap.java program (Listing 12.1) without
modification. Make it a descending queue (largest item is removed).
- Implement a linear probe hash table that stores strings. You'll need a hash function that converts
a string to an index number; see the section
Hashing Strings in chapter 11. Assume the
strings will be lowercase words, so 26 characters will suffice.
- Write a hash function to implement a digit-folding approach in the hash function (as described in
Hash Functions section 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?