Assignment #7 - Simple Maps and 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.
- Build more advanced data structures.
- 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 as quickly as possible so you can leave for Spring Break.
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 two classes for Map implementations, LookupTable.java, and
HashTableMap.java. It also provides a class for Dictionary implementation
Logfile.java, and includes an abstract and concrete class for using the Dictionary as a
Map. The net.datastructures package contains all of the interfaces needed for this
assignment.
- Complete the Logfile by using methods from the Linked Sequence
(we have provided a complete and correct version of the Linked
Sequence). The Unsorted Map will use your logfile. You do NOT need to change the UnorderedMap class, though if you use it as part of your Hash Table, be sure to analyze and document times correctly.
- Complete the Lookup Table by using in-place insertion and binary search.
- Complete the Hash Table. Be sure to conceptualize the structure so it is easier to complete the basic functions of the Hash Map. For the iterators, you may find the code written for your Bucket Sort algorithm useful.
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