/ Programming II: Assignment
Using Hash Tables to Sort
Assignment Date: Tuesday, 1 March. Due date: Thursday, 17 March at 4:00pm
This assignment is the first of four you will have in this course.
mark in Programming II is composed of 40% coursework, 60% exam.
This assignment is worth 10% of your mark.
What to Sort & Search (and a note on plagiarism):
This assignment will build on some of the code you wrote for last
In particular, you should reuse the objects that you created to
sorted, and also the code that generates arrays full of those objects.
you have not completed last week's tutorial, you need to start off by
instructions 3 & 4 of that tutorial. If you have completed
tutorial but the code is in your partner's directory, either rewrite it
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.
note on plagiarism:
Plagiarism occurs any time that you use someone else's ideas
acknowledging them. Plagiarism is much, much worse than asking
If you get help on any part of your assignment you should
this in the
This includes asking coursemates, tutors, or other staff, as well
reading things in books or on the Internet. Say exactly where
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
your initial object, or else explain why you didn't use the code you
in tutorial. We will be looking for this comment!
What to do:
NOTE: As I said in lecture
7, the `correct' (neat) way to
do this assignment would be with two classes -- one for the sorted
objects, and one for generic hashes. However, I am requiring in
the coursework that you demonstrate an ability to use class variables
and instance variables in the same
class! This allows you to prove you understand the
difference between class and instance variables. If you would
prefer to write it another way (and for good reason, see the notes
above), please write about this in the analysis. See particularly
the description of distinction projects.
But still do it as described here.
- Write an informal specification of your class. It should
- 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
- The method for generating an array of different lengths of
objects with random key values (this is also from last week).
- A class variable hashTable.
- A class method called hash which generates a hash-value for any
- Your hash function should be: hash(key) =
key mod 20. Make sure hashTable is the appropriate size
for this function!
- 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.
- Note: There's no reason to sort elements that are in a
together --- there should always be few enough that you can look
them in constant time. Look at the analysis part of the lecture!
- 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
you can get a good pass if you store all the instances but only ever
the first one you stored. If you want to move towards
feel free to think of a more clever way to deal with this, such as
a second key, or rejecting key values that already exist in the hash,
- A class method called hashStore which puts an object into the
hash table, using the hash function.
- A class method called hashFind which takes a key and returns an
object or null if no such object is in the table.
- Write the code for your new class.
- Test your class!
- You will be testing your function on arrays of size 12, 14, 16
& 18 of your class.
- For each array size, do the following
- Generate the array.
- Print out the key values & save them somewhere.
- Use hashStore on each object in the array (you probably want
to write a method to do this for you!)
- For each number from 1-10, check to see:
- Does the function correctly say whether the number is in
- How many objects did hashFind look at before it gave you
right answer? (you will have to make hashFind report this number
New Note: As will be
discussed in class on 9 March, we have decided both two class & one
class solutions to the hash part of this problem are acceptable provided that the hash table is
still a class variable.
What to hand in:
- Your informal description of your classes & algorithms.
A printout of your fully-commented code.
- Note that we expect this to have been written before you
have done the coding, so it may have bugs in it!
A short write-up of the results of your tests, including some
about how well the different-sized arrays worked with your hash
- Poor program layout will lose marks.
- Poor coding will lose marks.
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.
- Show your essential results 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.)
- Be sure to include instructions for how to replicate your
we will also be running your program to check on it.
- Be sure to include a printout of some sample output printed by
- Be sure to include some written analysis of how your program
performed, especially if your expected results did not match your
Remember, marks are not given just because a program compiles or runs.
should run robustly, and it should be well commented & well
make the program take a command line argument for the length of the
list (# of things to be sorted) for the test cases (12...).
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
this is a late addition, you won't get marked down if you don't do it,
but you will have a happier
How you will be marked:
The marks allocation for this assignment is as follows:
- Description / Specification 15%
- Fully commented, working programs implementing your design
- Results and analysis 25 %
- Brief discussion of requirements and program design.
- Simple program. Basic level of commenting. Code layout is mostly
correct. Code does the minimum possible functionality; much
running and testing must be done by hand.
- Minimum of results, but results are largely correct. Some
conditions not tested.
- Little or no analysis.
- Specification covers all aspects of problem. Good program design.
Algorithms are given at an appropriate level of
detail and are well explained. Clear description of how design will be
- 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.
- Results are correct, clearly described, and include good
- Some discussion of the program and the development
process you undertook, ideas for improvement.
- Specification covers all aspects of problem. Detailed
program design starting with a high level design and showing
refinement into appropriate levels. Algorithms are given at an
level of detail and are well explained.
- A sophisticated program showing good use of Java, but not overly
Commenting is appropriate and gives sufficient information. Layout of
is correct and clear.
- Results are clear and presented in an interesting way. Results
are sufficient to give scope for excellent analysis.
- Excellent analysis of results,
possibly considering alternative
implementations. Shows a thoughtful discussion of the program and
process you undertook. Detailed and
thoughtful criticism of your work, and well-thought-out ideas for
page author: Joanna Bryson
checked by AMB for release, 28 February
updated 8 March