https://drive.google.com/drive/folders/1lazm459K6Y9PhKGld6CJAwYdRbB3IzRn?usp=sharing
CSC311, Data Structures
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 in Chapters 6 and 7, the
actual assignment should not be very challenging, but you need to be aware of the dierent components
that will be required for all assignments. This means that you are allowed to use the code example, but
make sure to properly cite your textbook in your project.
Objectives
The main objectives of this assignment are:
Implement abstract data structrue List with array.
Implement abstract data structrue PositionalList with DOUBLY linked list.
Implement abstract data structrue Queue with CIRCULAR array.
Use JUnit test to debug and test each method.
Use good programming style and write good comments.
To complete this assignment, follow the steps listed below:
1.
Prepare the environment
Download and import the zip le: PA2.zip for Eclipse:
(a) Open Eclipse
(b) Select File, then Import
(c) Select General category
(d) Select Existing Projects into Workspace, and then click on Next
(e) Select the button for “Select Archive File” and browse to/select the zip le.
(f) Click on Finish. A new project List has been added to the workspace.
2.
Review Programming Assignment 2
Now, that you have added the project to your workplace:
(a) First, study the net.datastructures package. You will nd many interfaces. We will use a few
of these interfaces for this assignment (PA2), and the next assignment (PA3). For this programming assignment, you should only examine Queue.java, Position.java, PositionalList.java
and List.java in detail. Read comments and JavaDoc carefully and clearly understand what
each method does.
(b) Next, study the csc311 package. You will see the following 3, almost empty, java classes:
DoublyLinkedList.java, ArrayList.java and CircularArrayQueue.java. These are the three java
classes that you need to implement correctly.
(c) Last, but very important, study the JUNIT test source code under folder tests/ArrayList and
tests/DoublyLinkedList. Make sure you understand the test setup and how each test case is
written. You should make sure that your code pass all these test cases. You are encouraged
(not required) to write more test cases when ever you nd a situation that the existing test
cases does not cover.
3.
Implement ArrayList.java
4.
Implement DoublyLinkedList.java
5.
Implement CircularArrayQueue.java
6.
Write good comments
7.
Test your code
While you are implementing the above three les, besides typing the
source code, you should also Write good comments to document source code. See the comment
before the for loop in the example below. Please note you don’t need to copy the Java doc from
interface. I copied the header comment here so you can understand method remove(int).
Test, Test, and Test!!! Test your code. Remember try to implement one method
and test it before you implement another method! Identify the related test cases under folder tests,
and run them every time you thought you completed a method. You are encouraged to create
more Junit test cases or use simply create main method and/or other methods to test your code.
2
Important Notes:
NEVER, ever, ever modify ANY classes in the net.datastructures package. Don’t create new
les, don’t remove le from net.datastructures. We overwrite this package with the originals
when we test your code.
DO NOT change the class and method signature for the CircularArrayQueue, DoublyLinkedList
and ArrayList class. They need to stay as-is. Don’t change the number of the arguments,
the type of each argument, the order of the arguments. Don’t change the return type. Don’t
change access modiers.
You may create your own class les, main method and other methods for implementation or
testing purpose. If you create constructor, make sure it is PUBLIC, otherwise your program
may break when we test it. You should clean up your code before you submit, especially
you need to remove all your debugging System.out.print statements in the methods that we
asked you to implement. Those print statments will cause your program takes much longer
to nish. They will aect the performance when we test the eciency of your code, and
they may even cause the testing code to timeout. But you may keep your main methods and
testing methods in place. It is totally ne to have print statements in your main methods or
testing methods, because we don’t run them when we grader your code.
Make sure you understand generic types (the E and ) in the source code. Refer to Sun’s
tutorial: Generics
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];
8.
Submit your project:
(a) Before submission, be sure to review the following checklist:
Will your project easily import to Eclipse? (Make sure to export your project as a single
.zip le exactly like PA2.zip that has been provided to you. See below instruction for
more information about exporting your project)
Does you programs compile without errors? (Programs that don’t compile will not be
graded)
Is the indentation easily readable? You can have Eclipse correct indentation by highlight-
ing all code and select “Source
Correct Indentation”.
Does the program meet all required interfaces?
Are comments well organized and concise?
(b) If you have reviewed your code and all the criteria on the checklist above are acceptable,
follow the following procedure to export the les. For Eclipse:
i. Open Eclipse, and choose File, then Export
ii. Select General, and then Archive File
3
iii. Click Next
iv. Click the down arrow for project “List”, check the box next to src.
v. Browse for the destination/enter the archive le name as PA2.zip (not .rar)
vi. Click on “Finish”
vii. le PA2.zip List will be created under the destination of your choice.
(c) Double check the zip le has the correct folder structure and ALL the java source code les
are under the correct folders. Missing any source le or directory could cause compilation
failure. When the project does not compile, you will get 0 point. For example, for the
rst assignment, the zip le should have folder list/src/csc311 and all the source les under
csc311.
(d) For the submission, login to Blackboard and upload your PA2.zip to the appropriate assignment. You may submit many times, the latest submission will be graded only.
Grading Criteria
CircularArrayQueue, ArrayList and DoublyLinkedList that correctly implements all the required
interfaces methods: (80 Points).
Clear concise code with consistent style (10 points).
Good commenting (10 points).
When the project does not compile (-100 points)
FAQ
Is the ArrayList xed size or is the ArrayList resizable?
It is resizable. The initial size could be set
as 16 as the text book suggested.
How should I expand the ArraySize?
Do I need to shrink the array?
Double the size once it reaches its capacity.
Not needed for this assignment.
Does the data in the array has to be stored continuously?
Can we put NULL to some array cells ?
Yes.
Yes. ArrayList does not care what data you store in each
array cell.
4