Due Date: Thursday of week 15

The following guidelines are expected for all homework submissions:

• 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, peripherals, and applications, and could make code that is nicely formatted on *your* computer look all over the map on *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.
• On assignments 1, 2, and 3, WORK BY YOURSELF. On assignments 4 and 5, YOU MAY WORK IN A GROUP if you would like to do so. However, I can't stress this enough; part of this policy is don't split up the work – YOU MUST WORK TOGETHER on the assignment if you work together!. 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 within your group as much as you want, doing the entire assignment together.
• DO NOT share your work between individuals or 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 level and you don't share your code between groups or individuals. Each person or group needs to turn in its own version of the solutions.
• Submit your assignment in GitHub, in your repository, to which I must be invited to be a collaborator. I cannot evaluate what I cannot see!
• If you are working in a group you only need to turn in ONE COPY per group.
• MAKE SURE YOUR GITHUB REPO IS PRIVATE [for reasons explained on the syllabus page and in class].
• MAKE SURE TO INCLUDE ME IN YOUR REPO AS A CONTRIBUTOR so that I can upload your evaluations.

Problems for Assignment #5

Learning Outcomes: 1) implementing the tree traversals; 2) implementing a priority queue data structure using a heap data structure; 3) implementing a hash table that uses linear probing; 4) writing your own hashing method algorithm and testing it; 5) using different data structures in concert to solve a problem

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:

1. [This is a review problem to help you get ready for learning about graphs.] Write a method that does an in-order traversal 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 subtree.
2. Implement the PriorityQ class in the PriorityQ.java program [Listing 4.6 of the Java book] 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, except for translating it from java into python. Make it a descending queue [largest item is removed].
3. 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.
4. Write a hash function to implement a digit-folding approach in the hash function [as described in the 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. Answer the question: Does it matter if the array size is not a multiple of 10?