CS2321 Spring 2016: Assignment #1 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 ) 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.
