Assignment #7 - Simple Dictionaries
This assignment may seem easy, but it requires strong OO design. You
should read through the assignment to get a basic idea of the requirements
and then start working through the assignment in the recommended order.
Objectives:
The main objectives of this assignment are:
- Continue to analyze data structures using the @SpaceComplexity and @TimeComplexity annotations.
- Practice reusing code to save time and energy.
- Provide you with a data structure implemented three different
ways which can be used later in the semester.
- Develop test cases to verify your own code.
The Assignment:
The Concept:
Finish a program quickly to be used for the next assignment.
Your Job:
Code up a logfile, a lookup table and a hash table. You will be
reusing old code to complete these as quickly as possible. You will be responsible for testing the code yourself, instead of being given a test platform.
Getting Started (and Getting Finished):
- Download and import the following zip file:
Assignment7.zip. For Eclipse:
- Open Eclipse
- Choose "File → Import"
- Select the "General" category
- Pick "Existing Projects into Workspace"
- Click on "Next"
- Select the button for "Select Archive File" and browse to/select the zip file.
- Click on "Finish"
- A new project has been added to the workspace which
provides three classes for Dictionary implementations, Logfile.java, LookupTable.java, and
HashTable.java. The net.datastructures package
contains all of the interfaces needed for this assignment
(including Sequence, Dictionary, and all of their
superinterfaces).
- Complete the Logfile by using methods from the Linked Sequence
(we have provided a complete and correct version of the Linked
Sequence).
- Complete the Lookup Table by using in-place insertion and binary search on a dynamic array.
- Examine the provided code for the Hash Table - try to
understand the given structure so it is easier to complete the basic
functions of the Hash Table. For the iterators, try using the code
written for your other Dictionaries and Bucket Sort algorithm (it shouldn't take much
adjustment).
Submission:
First, look at the following checklist:
- Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
- Do you ever import from java.util. If so, be sure you only
import allowed components (like Iterator, Exceptions, etc.). Unless
the assignment specifically mentions it is permissible, you should never include
any of java's native data structures.
- Does the program meet all required interfaces?
- Do all your methods have a @TimeComplexity indicator?
- If any methods have a good amortized or expected cost, do they have both
the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
- Do all your data structures (and other classes like iterators) have a
@SpaceComplexity indicator?
- Do you provide adequate TCJ and SCJ comments
to prove your time and space complexity?
- Is the indentation easily readable? You can have Eclipse correct indentation
by highlighting all code and select "Source → Correct Indentation".
- Have you removed any of the "cs2321" comments (/*#) that you
may have accidentally copy/pasted?
- Are comments well organized and concise?
If you have reviewed your code and all the criteria on the checklist are acceptable,
follow the submission procedure.
Grading Criteria:
- An Logfile, LookupTable, and HashTable, using the code given, correctly implementing all methods and
interfaces: 75 (25 points each)
- Correct documentation of time and space complexity: 15
- Clear concise code with good commenting: 10