Assignment #1 - Index List, Position List, Time Complexity and
CS2321 Style
Read through the assignment to get a basic idea of the requirements and then start working through the assignment in the recommended order. With the code example in the
text book, the actual assignment is simple, but you need to be aware of
the different components that will be required for all assignments.
Objectives:
The main objectives of this assignment are:
- Implement abstract data structrue index list with array.
- Implement abstract data structrue position list with doubly linked list.
- Use good programming style and write good comments.
- Annotate the method with time complexity @TimeComplexity and
write brief justication.
- Make sure everyone is well prepared for the remaining assignments.
The Assignment:
- Download and import the following zip file:
Assignment1.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 List has been added to the workspace:
- Study the new project. First, look at the net.datastructures package. You will
find all the interfaces that we will cover this semester there. Examine
the PositionList.java and List.java in detail. Read comments carefully
and understand what each method does clearly. Then, look at the cs2321 package. You will see an almost empty DoublyLinkedList.java and ArrayList.java. These are the two java classes that you need to implement correctly.
- Make sure you understand generic types (the E and
<E>) in the source code. These will be/were explained
in class, but Sun's tutorial may also help:
Generics.
- Implement ArrayList.java.
- Implement DoublyLinkedList.java
- While you are implementing the above two files, besides typing the source code, you should also
- Write good comments to document source code.
- Add time complexity annotation taken by
methods (@TimeComplexity) before each method. Justify the time complexity inside the method body with TCJ
- Test your code. Write main method and/or other methods to test your code. You are encourage to write Junit test cases to test your code.
- These are essential for full credit on programming assignments.
- NOTE THE FOLLOWING:
- Never, ever, EVER modify ANY classes in the net.datastructures
package. We overwrite these files with the originals when we test
your code.
- DO NOT change the class signature for the DoublyLinkedList and ArrayList class. It
needs to stay as-is.
- In both class, Constructor takes no argument. Make sure it is PUBLIC, otherwise your program will break when we test it.
- Java Generics can be really picky when it comes to arrays.
In order to initialize a generic array to store objects of type E,
where E is a formal type, you will need to do:
myArray = (E[])new Object[numberOfElements];
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 the main methods have a @TimeComplexity indicator?
- Do you provide adequate TCJ comments to prove
your time complexity?
- Is the indentation easily readable? You can have Eclipse correct
indentation by highlighting all code and select "Source → Correct
Indentation".
- 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:
- ArrayList and DoublyLinkedList that correctly implements all the required
interfaces methods: 60 Points.
- ArrayList and DoublyLinkedList have been implemented efficiently: 10 points.
- Use of appropriate tags on all methods to indicate
complexities (@TimeComplexity ): 10 points.
- Clear concise code with good commenting including the time
complexity justification: 20 points.