CM10135 / Programming II:   Assignment 1 (2007)

Manipulating Memory:  Hash Tables to Sort & Search

Assignment Date:  Tuesday,  14 February  Due date:  Tuesday, 28 February at 4:00pm

Objectives:

What to Sort & Search, and a note on plagiarism:

Phase I:  What to do

1. Write an informal specification of your hash & hashable object classes. 
   
1. MySortableObject (from the objects you sorted in your tutorial last week) should include:
   
1. The key attribute you are using for your sort (e.g. age if you used last week's defaults).  Only this time, make sure the maximum key size is exactly 35 (even if this means you have old children!).
   
2. A method key that returns the key value.
2. MyHash should include:
1. An instance variable hashTable.
2. A class method called hash which generates a hash-value for any integer key.  
1. Your hash function should be:  hash(key) = key mod 22.  Make sure hashTable is the appropriate size for using this function!
2. Be sure to implement some simple method for dealing with collisions!  Two possibilities were described in last week's lecture, I expect you will probably use the one described in the notes where that link points to.  
1. Note: There's no reason to sort elements that are in a bucket together --- there should always be few enough that you can look through them in roughly constant time.  (Look at the analysis part of the lecture.)
2. Note: Because you are generating your key values randomly, you may have two objects with the same key value!  Feel free to ignore this if you want; you can get a good pass if you store all the instances but only ever retrieve the first one you stored.  If you want to move towards distinction, feel free to think of a more clever way to deal with this, such as employing a second key, or rejecting key values that already exist in the hash, etc.
3. A method called hashStore which puts an object into the hash table, using the hash function.
4. A method called hashFind which takes a key and returns an object or null if no such object is in the table.
3. The driver function should include:
1. your main function,
   
2. a method for generating an array of different lengths of objects with random key values (this is also from last week's tutorial), and
   
3. it should accept a command line argument for how many objects you will be sorting.
1. See below for "test your classes" for more details of what this will need to do.
2. Write the code for your new class.
3. Test your classes!
1. You will be testing your function on arrays of size 14, 16, 18 & 20 of your class.
1. Don't forget, you should be able to do this using a command line argument.  We will test your program with other values when we mark it!
2. Sorry, I used the word "arrays" here in the ordinary language sense.  N, the number of objects is 14, 16, 18 & 20 on different test runs.  You don't actually have to put these in an array.  However, you do need to record what the objects are somehow in order to run and check the tests below (step 2.5).
   
2. For each array size (really, value of N), do the following
1. Generate the array.
2. Generate an instance of MyHash to sort the instances.
   
3. For each element in the array:
1. print out the key value as part of the results,
   
2. use hashStore on each object in the array.
4. Now each instance of MySortableObject should also live in a single instance of MyHash.
   
5. For each number from 1-10, check to see:
1. Does hashFind correctly say whether the number is in the array?
2. How many objects did hashFind look at before it gave you the right answer?  (you will have to make hashFind report this number to you.)
4. Analyze your results:
1. What was the average number of items that hashFind needed to check for each array size?
   
2. How close did hashFind come to a constant-time search?
3. Did the analysis of hash table statistics you learned in lecture predict your results?
   

Phase II:  What to do

1. Create a class variable for MyHashedClass.
   
2. Make sure hashStore & hashFind are class methods.
3. Make certain that whenever you add a new instance of MyHashedClass, a call to hashStore is made.
4. Be sure to write a main function for this class!  This class is its own program all itself.
   
5. Be certain not to make any calls to any of the classes you were using in Phase I --- MyHashedClass should be able to stand on its own.
   
6. Test your class on at least two of the array sizes you used before --- it should work just the same, except that you will be forced to start the program over to create a new hash.
   

What to hand in:

1. Your informal description of your MySortableObject, MyHash & their algorithms.
• Note that we expect this to have been written before you have done the coding, so it may have bugs in it!  Don't correct this, just comment on it in your analysis.  About 0.5-1.0 page.
  
2. A printout of your fully-commented code for all four classes. 
   
• Be sure to make a distinction between the two programs (one for each phase) you are handing in -- the first with three classes, the second with only one.
  
• Poor program layout will lose marks
•  be sure to use a fixed-width font on the code print outs.
• Use returns & indenting!
• No printouts in landscape -- print them in portrait like normal.
• No printouts with less than 10pt font size.
• All printouts on ordinary A4 paper.
• This makes it easier to read your code in your editor anyway.
  
• Poor coding will lose marks, e.g. extraneous code, sorting the inputs before hashing them, other silliness. 
  
• You should clean up your code once you get it working just like you would clean up the first draft of an essay before handing it in. 
  
• You should do this cleanup right after getting Phase I working;  that will make it easier to then do Phase II.
  
3. A short write up of the results of your tests, including some analysis about how well the different-sized arrays worked with your hash function. 
   
• Show your essential results from phase I in a table (like a test plan from software engineering) with the conditions running down the left hand side, and columns for the test parameters, expected results, actual results, and efficiency of the search (number of objects searched.)
• For Phase II, it's enough just to say the code works the same (assuming it does.)  Just report which values you tested it on.
  
• Be sure to include a printout of some sample output printed by both programs.
• "Sample output" should not be a screen shot.
• Redirect output to a file & print that.
  
• Be sure to include some written analysis of how your program performed, especially if your expected results did not match your actual results!
• The entire results & analysis write up should be from 1.0 to 2.5 pages.  Excessively long write ups will be penalized just as much as excessively short ones.
  
4. A zip file containing uncompiled versions of your code.
   
• The person marking your program will be compiling & running your program.
• Be sure to include instructions for how to replicate your tests, since we will also be running your program to check on it.
• Make sure the program takes a command line argument for the length of the list (# of things to be sorted) for the test cases.   This will make it easier to test for the tutor/markers to run it.  Don't do elaborate exception testing for this, just check that you got a number passed in.

How you will be marked:

1. Informal Specification 10% 
2. Fully commented, working programs implementing your design 70% 
3. Results and analysis 20 % 

1. Brief discussion of requirements and program design.
   
2. Simple program. Basic level of commenting. Code layout is mostly correct.  Code does the minimum possible functionality (maybe even less if exceptionally well commented & analyzed); much running and testing must be done by hand.
   
3. Minimum of results, but results are largely correct.  Some conditions not tested.
   
4. Little or no analysis.
   

1. Specification covers all aspects of problem. Good program design. Algorithms are given at an appropriate level of detail and are well explained.
   
2. Program is a good implementation of design, or possibly better than the design. Layout of code is correct and clear. Code is generally concise but comprehensible, identifiers well named.
   
3. Results are correct, clearly described, and include good analysis. 
4. Some discussion of the program and the development process you undertook, ideas for improvement. 
   

1. Specification covers all aspects of problem. Algorithms are given at an appropriate level of detail and are well explained. 
   
2. A sophisticated program showing good use of Java, but not overly complex. Commenting is appropriate and gives sufficient information. Layout of code is correct and clear. 
3. Results are clear and presented in an interesting way. Results are sufficient to give scope for a strong analysis. 
4. Excellent analysis of results, possibly considering alternative implementations.  Shows a thoughtful discussion of the program and the development process you undertook. Detailed and thoughtful criticism of your work, and well-thought-out ideas for improvement.

Marks Table: