Algorithms and Data Structures I

Project 1: ReallyLongInt

Background

Note: All starter files will be shared in a link at the end of this document.

In this project, we will use what we’ve reviewed about object-oriented programming in Java in combination with the Bag ADT from lecture to create and use a 2D array-based data structure.

Your Task: Design and implement a generic class (ArrayDS<T>) that will act as a data structure for accessing sequences of Java Objects. Your ArrayDS<T> class will primarily implement SequenceInterface<T>. The

details of this interface is explained in SequenceInterface.java  . Readthis over very carefully before implementing your ArrayDS<T> class.

ArrayDS

For the details on the functionality of your ArrayDS<T> class, carefully read over the files

SequenceInterface.java and Project1.java. You must use these files as specified and cannot remove/alter any of the code that is already written in them. There are different ways of implementing the

SequenceInterface<T> interface methods, some of which are more efficient than others. Try to think of the  best way of implementing these methods in this assignment, but the most important thing at this point is getting them to work correctly. A lot of pencil and paper work is recommended before actually starting to write     your code. Later we will discuss the relative merits of different implementations.

Important Note: The primary data within your ArrayDS<T> class must be a two-dimensional array. You may   not use any predefined Java collection class (e.g., ArrayList) for your ArrayDS<T> data fields. You may not declare and/or use any one-dimensional arrays except in the toArray() and hasSub sequence()

methods. Any methods besides these three will only be eligible for 50% credit if they are found to use one-dimensional arrays. This will be applied after the project is due!

You must use the following instance variables inside the ArrayDS<T> class:

private final BagInterface<Integer>[] [] array; //the underlying 2-D array

private int size ; //the number of items in the sequence

private T [] alphabet ; //the possible item values (e .g ., the decimal digits)

private T firstItem; //the first item in the sequence

private T lastItem; //the last item in the sequence

You should add other variables and named constants to follow the secure programming practices we mentioned in class.

To illustrate how to store a sequence of objects as a two-dimensional array, let's have an example.

Let's take the sequence 9875732732 as an example. This is a sequence of decimal digits. The sequence alphabet is the set of possible values from which the sequence items are drawn. So, in this example the alphabet is the set of decimal digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. This sequence can be visualized like this:

Each of the ten digits of the alphabet is represented by a circle. Every pair of consecutive digits in the sequence results in an arrow in the diagram, and the arrow's label includes the position of the second digit in the pair. For example, because 9 is followed by 8 in the sequence, there is an arrow from 9 to 8 in the diagram. Because the position of 8 in the sequence is 1, the arrow from 9 to 8 has 1 in its label. Because 3 is followed by 2 twice in the sequence, the arrow from 3 to 2 is labeled by 6 and 9, the positions of 2 in the sequence in both occurrences of 32 in the sequence.

To construct the sequence from the diagram, we follow the arrows starting from the firstItem (9), then 8   then 7. With each step, we keep track of our position in the sequence. At 7, we are at position 2 and we have  to decide whether to go to 3 or to 5. We go to 5 because of the label {3} of the arrow from 7 to 5, indicating   that 5 is at the next position (3). We keep following the arrows until we reach the last item. The circles that we will go through represent the sequence.

Here are some properties of the sequence in the example above. Please match these with the methods in SequenceInterface.java:

The diagram above (which, by the way, is called a graph) is represented as an NxN two-dimensional array, where N is the size of the alphabet, which is 10 in the example. The array representation of the diagram above is:

Each cell at row i and column j in the array contains the label of the arrow going from item i in the alphabet to item j in the alphabet. If there is no arrow between i and j, the cell is empty (null). Each cell is a BagInterface of Integers.

The sequence after append(7) will look like this:

Its array representation is:

After prefix(0): 

You will also need to override the following method. You might find it helpful to implement this first so you can use it while debugging your other methods:

public String toString() ;

This method will return a String that is the concatenation of all of the items in the Sequence implemented by the ArrayDS object appended together without spaces. For example, if an ArrayDS object contains the numbers 1, 2, 3, 4, 5, 6, toString() should output 123456.

To check your implementation of ArrayDS<T>, the Project1.java file should compile, run, and give output identical to P1Out.txt. Please note that this statement doesn't suggest that you delay testing until you are done with all the methods of ArrayDS. Instead, you should use stubs (comment out what you haven’t implemented  yet) and incrementally test your code using Project1.java as you complete each of the methods.

Starter Code

All starter code (including the shell of ArrayDS.java) and example output is available for download from this folder:

https://drive.google.com/drive/folders/1_Z85TGqy_noblGr3jhQBhR2gEnd12B7z?usp=sharing

Deliverables

You are responsible for submitting ONLY ArrayDS .java.  All other files will be automatically supplied to Gradescope. I would suggest avoiding making code changes to any of the other files (besides stubbing out Project1.java to test parts of your implementations at a time as you work).

If you use Eclipse or any other Java IDEs to work on this project, remember to test on a command line before submitting. Sometimes editors add package lines to the top of  .java files that will break the autograder.

Hints

-    See file P1Out.txt to see how your output for task A should look. As noted, your output when running

Project1.java should be identical to this.

-    In order for the Project1.java output to show correctly, you must override the toString() method in the ArrayDS class.

-    Think carefully about the order in which you implement ArrayDS methods as some methods can make others considerably easier to implement!