My ArrayList 2

Introduction

In this lab, you will get some practice implementing certain methods of an expandable, generic MyArrayList data structure and doing an amortized analysis of one of the methods thereof. Basically, in addition to the parameterized constructor, you have to implement the operations of isEmpty, add, grow and remove. Then, you will do a very simple amortized analysis, using empirical methods, to derive the worst-case running time of add when executed in a sequence of several add operations.

Note that there is a lot of "extra" code that is given. Don't modify any of the given code. I will need this for testing purposes.

Getting started

1. Create a new project in NetBeans called Lab5. Make sure you uncheck Create Main Class in the New Java Application window.

2. Within the default package of your Lab5 project, create a new Java class called MyArrayList and use the following code to get started (the following code is also available for download on Canvas as MyArrayList.java):

import java.util.Iterator; // Given
/**
* Write a description of class MyArrayList here.
*
* @author (your name)
* @version (a version number or a date)
*/
// Do not modify the given code.
@SuppressWarnings("unchecked") // Given
public class MyArrayList< T> {
private T[] data; // Given
private int size; // Given
/*
Implement. You must provide a comment block!
*/
public MyArrayList(int inCapacity) {
}

/*
Implement. You must provide a comment block!
*/
public boolean isEmpty() { }
/*
Implement. You must provide a comment block!
*/
public boolean add(T obj) {
// This method appends obj toward the back of data
// Always return true
}

/*
Implement. You must provide a comment block!
Implement this method so that a sequence of add operations
executes as efficiently as possible.
*/
private void grow() { }

/*
Implement. You must provide a comment block!
*/
public boolean remove(Object obj) {
// Return true if obj was removed from data
// and false otherwise.
}

/*
The rest of the code is given.
I will use it for testing purposes.
Do not modify!
*/

// Given. Do not provide a comment block!
public String toString() {
if (size == 0)
return "[ ]";
String retStr = "[ ";
for (int i = 0; i < size - 1; i++)
retStr += data[i] + ", ";
retStr += data[size - 1] + " ]";
return retStr;
}

// Given. Do not provide a comment block!
public boolean equals(Object obj) {
if (obj instanceof MyArrayList) {
MyArrayList< T> rhs = (MyArrayList< T>)obj;
if (size != rhs.size)
return false;
for (int i = 0; i < size; i++)
if (!rhs.contains(data[i]))
return false;
return true;
}
return false;
}

// Given. Do not provide a comment block!
private int find(Object obj) {
for (int i = 0; i < size; i++)
if (data[i].equals(obj))
return i;
return -1;
}

// Given. Do not provide a comment block!
public boolean contains(Object obj) {
return find(obj) >= 0;
}

// Given. Do not provide a comment block!
public void addAll(MyArrayList< T> inList) {
for (int i = 0; i < inList.size; i++)
add(inList.data[i]);
}

// Given. Do not provide a comment block!
private class MyArrayListIterator implements Iterator< T> {
private int index = 0;
// Given. Do not provide a comment block!
public void remove() { } // No implementation
// Given. Do not provide a comment block!
public T next() {
T temp = data[index];
index++;
return temp;
}
// Given. Do not provide a comment block!
public boolean hasNext() {
return index < size;
}
}
// Given. Do not provide a comment block!
public Iterator< T> iterator() {
return new MyArrayListIterator();
}
}

Follow the instructions in the Requirements section to see exactly what you have to do for this lab.

Requirements

Ensure that your lab satisfies the following technical requirements:

1. For the first part, fill in the missing details in the MyArrayList class, as indicated by the comments. It is your responsibility to ensure that the formatting guidelines are followed. For example, make sure you have a consistent indentation scheme. The only exception is that you do not have to provide comment blocks for certain methods. Do not modify any of the given code.

2. In the comment block for add, give the best possible big-O of the worst-case running time for executing a single add operations. Briefly justify your answer.

3. Also in the comment block for add, give the best possible big-O of the total worst-case running time of executing a sequence of N add operations. Hint: take your previous answer and multiply it by N. Briefly justify your answer.

4. Depending on what you put for the previous two parts, your answer for the previous step might be a bit too "pessimistic". In other words, even though the worst-case running time of a single add is O(??), such worst-case behavior does not happen all the time. So, for this final part, compute the worst-case running time of a single call to add, assumed to be executed during a sequence of N calls to add. Use empirical methods to derive your answer. For example, compute the total amount of time it takes to call add N times, and then divide by N and see what you get. Do this for several increasing values of N and try to spot a pattern. Or, you can count the the number of simple operations executed across a sequence N add operations and then divide the total by N. In the comment block for add, give the best possible big-O of the worst-case running time per call to add, assuming each call to add is one call in a sequence of N calls.

5. Finally, in the comment block for add, clearly and concisely justify the answer you gave in the previous part. Are you surprised by your findings in the previous part?