CM10135 / Programming II:   Assignment 1 (2004)

Using Hash Tables to Sort & Search

Assignment Date:  Tuesday,  24 February.  Due date:  Tuesday, 9 March at 4:00pm

This assignment is the first of four you will have in this course.  Your mark in Programming II is composed of 60% coursework, 40% exam.

What to Sort & Search (and a note on plagiarism):

This assignment will build on some of the code you wrote for last week's tutorial.  In particular, you should reuse the objects that you created to be sorted, and also the code that generates arrays full of those objects.  If you have not completed last week's tutorial, you need to start off by completing instructions 3 & 4 of that tutorial.  If you have completed that tutorial but the code is in your partner's directory, either rewrite it or ask your partner to email it to you.  Note: we will not be marking the sorts you wrote last week, we will only be marking the basic class and it's hash methods.

An important note on plagiarism:  Plagiarism occurs any time that you use someone else's ideas without acknowledging them.  Plagiarism is much, much worse than asking for help.  If you get help on any part of your assignment you should acknowledge this in the comments.  This includes asking coursemates, tutors, or other staff, as well as reading things in books or on the Internet.  Say exactly where your help came from, and exactly how much of the code is your own.  In particular, in this assignment, you should acknowledge your partner from last week for helping you to build your initial object, or else explain why you didn't use the code you wrote in tutorial.  We will be looking for this comment!

What to do:

  1. Write an informal specification of your class.  It 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 30 (even if this means you have old children!). 
    2. The method for generating an array of different lengths of objects with random key values (this is also from last week).
    3. A class variable hashTable.
    4. A class method called hash which generates a hash-value for any  integer key.  
      1. Your hash function should be:  hash(key) = key mod 20.  Make sure hashTable is the appropriate size for 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:  I've updated the lecture notes to make this more obvious, so you may want to push the reload button in your browser if that link doesn't take you right to the hash search algorithm section of the notes.
        2. Note 2: 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 constant time.  Look at the analysis part of the lecture!
        3. Note 3: 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.
    5. A class method called hashStore which puts an object into the hash table, using the hash function.
    6. A class method called hashFind which takes a key and returns an object or null if no such object is in the table.  
  2. Write the code for your new class.
  3. Test your class!
    1. You will be testing your function on arrays of size 12, 14, 16 & 18 of your class.
    2. For each array size, do the following
      1. Generate the array.
      2. Print out the key values & save them somewhere.
      3. Use hashStore on each object in the array (you probably want to write a method to do this for you!)
      4. For each number from 1-10, check to see:
        1. Does the function 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.)

What to hand in:

  1. Your specification / requirements statement.
  2. A design for your solution, including especially the algorithms.  Note that we expect this to have been written before you have done the coding, so it may have bugs in it!
  3. A printout of your fully-commented code.  Poor program layout will lose marks.
  4. A printout of output printed by your report.
  5. 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.  Be sure to include instructions for how to replicate your tests, since we will also be running your program to check on it.
  6. A conclusion that contains a critique of your program:  What did you do right?  What did you do wrong?  What would you do differently if you did it over?
  7. A disk containing an uncompiled version of your code.  Be certain the disk is not write protected!  The person marking your program will be compiling & running your program.
Remember, marks are not given just because a program compiles or runs.  It should run robustly, and it should be well commented & well documented as specified above.

How you will be marked:

The marks allocation for this assignment is as follows:
  1. Requirements statement 5% 
  2. Design of program solution 15% 
  3. Fully commented, working programs implementing your design 45% 
  4. Results and analysis 15 % 
  5. Conclusion/Critique 20 % 
Total 100%

Threshold Pass for each component
  1. Brief discussion of requirements. 
  2. Brief program design. Brief details of how the design will be implemented in Java. 
  3. Simple program. Basic level of commenting. Code layout is mostly correct. 
  4. Minimum of results, but results are correct. 
  5. Conclusion gives a brief, not very thoughtful discussion of the resulting solution. Little useful criticism and few ideas for improvement. 
Good Pass for each component
  1. Good requirements statement. 
  2. Good program design starting with a high level design and showing refinement into appropriate levels. Algorithms are given at an appropriate level of detail and are well explained. Clear description of how design will be implemented. 
  3. Program is a good implementation of design. Layout of code is correct and clear. 
  4. Results are clearly given with good analysis. 
  5. Conclusion shows a thoughtful discussion of the program and the development process you undertook and good analysis of the results. Sensible criticism of your work, and good ideas for improvement. 
Distinction Pass for each component
  1. Requirements statement covers all aspects of problem. 
  2. Detailed program design starting with a high level design and showing refinement into appropriate levels. Algorithms are given at an appropriate level of detail and are well explained. Excellent description of how design will be implemented. 
  3. 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. 
  4. Results are clear and presented in an interesting way. Results are sufficient to give scope for excellent analysis. 
  5. Conclusion shows a thoughtful discussion of the program and the development process you undertook and excellent analysis of the results. Detailed and thoughtful criticism of your work, and well-thought-out ideas for improvement.

page author: Joanna Bryson
set 23 Feb 2004
, most recent update 2 March 2004 (note 3 above)