Homework 09: SuperArrays

The goals of this assignment are:

• Practice designing classes
• Implementing an interface
• Comparing different approaches to sovle a problem

WARNING: In this assignment you are NOT ALLOWED to import any packages. For example, you cannot use the builtin Arrays java class to print out an array. Doing so will result in earning ZERO POINTS for a method that uses it.

IF YOUR CODE DOES NOT COMPILE, YOU WILL EARN 0 POINTS FROM THE AUTOGRADER.

1. Overview

In this last assignment, you will implement two classes: SuperDuperArray and SuperDuperSortedArray. These classes will implement the interface called SuperArray. We will provide you the interface called SuperArray that we provide.

You can find the interface here.

Both classes will keep track of an array of Strings.

For both of these classes, the toString() method should return one line that contains all the Strings. Each item should be seperated by a space. For remove, it should return a boolean indicating if the input element exists in the array or not.

2. SuperDuperArray

SuperDuperArray will be a wrapper around a String[]. Create a String[] as a private instance variable of your class. Implement a value constructor which takes one argument: int capacity. This will be the size of your array. Initialize your array instance variable in the constructor accordingly.

In addition to implementing all methods in the interface, SuperDuperArray, the class must include the following:

1. a method called String[] sort(int order) that takes in an integer to determine whether to sort in ascending or descending order. 1 means ascending and 2 means descending. The sort method must return a new sorted array. You are free to use Bubble or Selection Sort. You can use the built-in String methods for determining whether one String is greater than another.
2. The class must retain the order in which the elements were added.

2. SuperDuperSortedArray

Next, implement a class SuperDuperSortedArray which also implements the interface SuperArray. In this class, the array of elements must always be sorted. Each time an element is added, make sure the list stays sorted. One approach would be to add the element and then sort the elements. However, this approach would be O(n^2). For full points, come up with a faster approach.

Think about how you can implement remove and contains differently to be more efficient than in SuperDuperArray. For full points, add and remove should have a worst case complexity of O(n) and contains should have a worst case complexity of O(logn).

This class should also have a value constructor which takes a capacity.

README.txt

In a text file called README.txt answer the following questions:

1. Imagine you are building a program to keep records for a Vet. Which class would you rather use SuperDuperSortedArray or SuperDuperSorted? Make sure to justify your answer - there is no wrong answer here.
2. Next, make an argument for why it would be a good idea to use the other class that you didnt advocate for before.
3. List the Big O notation of the following methods for both SuperDuperArray and SuperDuperSortedArray: size, isEmpty, add, remove, contains, toString. For SuperDuperArray, list the Big O notation of sort.
4. How much time did you spend on the homework
5. What did you learn from this homework
6. optional: What did you struggle with during this homework
7. optional: any other feedback you would like to share

Submitting

Submit the following files to the assignment called HW09 on Gradescope:

1. SuperDuperArray.java
2. SuperDuperSortedArray.java
3. README.txt

Make sure to name these files exactly what we specify here and name the methods exactly what we specify too. Otherwise, our autograders might not work and we might have to take points off.