Assignment #3 - Sequences, Shelving, and Step Count.

Objectives:

The main objectives of this assignment are:
• Give you some experience analyzing algorithms
• Let you develop an implementation of a Sequence for a specific task
• Put your trust in the 3 laws of robotics.

The Assignment:

The Concept:

B&C Corporation has been awarded a contract to run a library. They've decided to try cutting costs by avoiding labor costs. Their original plan was to use zombies to reshelve the returned books. Unfortunately libraries attract brainy people and zombies have a propensity for eating brains. After numerous lawsuits were settled, B&C decided:
• The living want wages (and B&C doesn't want to pay).
• The living-dead lead to expensive lawsuits/settlements.
• The dead don't work (and the stench is unbearable)
This left only one option: robots.

Following their usual business practices, B&C purchased the cheapest killer robot on the market to take care of the zombies.  Then, they took the killer robot's arm off to shelve books. When given a load of books, the arm will travel up and down the shelves of the library carefully putting away the books. If the robot arm isn't properly reset after every 100,000 meters of travel, it will start up its flamethrower (which is undesirable in a building filled with paper). It's important to keep track of the robots total travel distance to ensure that it is maintained properly. In addition, the ancient computer used to control the robot arm is prone to overheating (and catching fire). It's critical that the code used to estimate travel distance be as efficient as possible to avoid overheating the system. And that's where you come in.

Your Job:

You have four tasks:
1. Analyze the complexity of the RobotArm. Its complexity may depend on the methods and implementation of the Sequence it uses. Use the annotation syntax (@TimeComplexity) and comments (// TCJ: ...) to clearly document the complexity of the RobotArm.
2. Choose an implementation for the Sequence. There are multiple possible implementations, but shelve() and retrieve() are hard-coded into the RobotArm, so you should try to pick a Sequence implementation that works best (least time complexity) for those two components.
3. Develop the Sequence data structure that will work with B&C's RobotArm.  A class file has been provided for you for two potential implementations: An Array based version (ArraySequence.java) and a Linked List based version ( LinkedSequence.java). When you chose which route to pursue, put all the required code for your Sequence in the appropriate file. (Leave the other version alone). You should NOT change the class names, interfaces, or packages (all these would prevent B&C from including the Sequence in their packages) and all your changes should be contained in just two files: one for the sequence and RobotArm.java.
4. You retain ownership of your Sequence implementation. It is important that all operations work correctly so you can use it in future projects (Assignments). Actually, it is pretty likely that some future assignments will require a good Sequence.

Getting Started:

1. Download and import the following zip file: Assignment3.zip. For Eclipse:
   1. Open Eclipse
   2. Choose "File → Import".
   3. Select the "General" category.
   4. Pick "Existing Projects into Workspace"
   5. Click on "Next"
   6. Select the button for "Select Archive File" and browse to/select the zip file.
   7. Click on "Finish"
   8. A new project has been added to the workspace: RobotArm, which provides a complete implementation of the RobotArm (RobotArm.java in the default package), and two classes for potential Sequence implementations, ArraySequence.java and LinkedSequence.java, both located in the cs2321 directory.
2. Review the Sequence methods used in the shelve() and retrieve() methods. Analyze the time complexity for the two potential implementations of a Sequence.
3. Implement one of the two potential Sequences. One of the implementations will perform better than the other. If you chose the worse implementation, you will lose 10 points.

Hints:

• If you use an array based implementation, be sure you have good amortized time when and where possible.
• If you use a linked list implementation, use sentinel nodes to mark the beginning and end of the sequence.
• Start off small: Implement an add and corresponding remove and test them.
• Work incrementally - as you complete new methods, test them.
• Some methods can be easily implemented using other methods. For instance, first() could use getFirst() or vice versa.
• If you are implementing an Array based structure, start with the methods in the IndexList interface.
• If you are implementing a Linked structure, try the PositionList interface first.
• Most of the methods in one interface can easily be created from methods in the other and either atIndex() or indexOf().
• Test for exception handling.

Submission:

First, look at the following checklist:
1. Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
2. 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.
3. Does the program meet all required interfaces?
4. Have you tested every method in some way?
5. Do all your methods have a @TimeComplexity indicator?
6. If any methods have a good amortized or expected cost, do they have both the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
7. Do all your data structures (and other classes like iterators) have a @SpaceComplexity indicator?
8. Do you provide adequate TCJ and SCJ comments to prove your time and space complexity?
9. Is the indentation easily readable? You can have Eclipse correct indentation by highlighting all code and select "Source → Correct Indentation".
10. Have you removed any of the "cs2321" comments (/*#)?
11. 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:

• A Sequence that correctly implements all methods and interfaces: 60
• Correct documentation of time and space complexity: 15
• Choosing the best implementation of Sequence for this problem: 10
• Clear concise code with good commenting: 15