CSCI 151 Lab 3: Extensible arrays

Overview

This lab will give you chance to become more familiar with extensible arrays, and to experiment with different methods for increasing the available storage space when they become full.

Materials

Setup

Create a new project in Eclipse called Lab03 (or something similar; really it does not matter what you call it).
Download ExtensibleIntArray2.java and copy it into your new Eclipse project, e.g. by dragging and dropping it into the src package.

Part 1: Generalizing

Our first step will be to generalize our extensible arrays so they can store any type of values, instead of only int values.

Make a copy of ExtensibleIntArray2.java and call the copy ExtensibleArray.java.
Edit ExtensibleArray.java and change the type of elements from int[] to Object[].

Object is a special Java class which is a superclass of every other class. This means that—just like Counter and LoudCounter were both Tickish, so we could store both in a Tickish[] array—everything is an Object, so we can store anything we want in an Object array. This is very much like Python lists, where we can store whatever we want, even things of different types. (There is an even better solution available in Java which we will learn about soon—but we must first understand the downsides of this simple Object approach.)
Go through and change remaining occurrences of int to Object as appropriate.
Congratulations! Your ExtensibleArray should now be able to store anything, not just integers.

Part 2: Word munching

Create a new class inside your project called WordMunch, with a main method.

The main method should prompt the user to enter some words, and then tell them

the longest word they entered,
the average length of the words entered, and
the words which were longer than the average.

Make sure to read the rest of the notes in Part 2 before starting to implement main! Below is shown a sample run of the program. Be sure that your program adheres as closely as possible to the output format shown.

Please enter some words, or "quit" when done.
help
me
I'm
stuck
inside
a
word
munching
program
quit
You entered 9 words.
The longest word, "munching", has length 8.
The average word length is 4.444444444444445.
The longer-than-average words are:
stuck
inside
munching
program

A few notes:

Of course, you should use an ExtensibleArray to store the words entered by the user.
To get input from the user:
- Add import java.util.Scanner; to the top of your code
- Create a new Scanner object which will read from the keyboard with
```
Scanner scan = new Scanner(System.in);
```
- Read each line entered by the user with the nextLine method of Scanner, like this:
```
String input = scan.nextLine();
```
When you retrieve an element from an ExtensibleArray, it will have the type Object. This means that something like
```
String word = myArray.get(i);
```
will not work—even if you know the object stored at index i is a String—because all Java knows is that it is an Object, and not every Object is a String. The solution is to use a cast to inform Java what type the retrieved element should be:
```
String word = (String)myArray.get(i);
```
(Of course, if the thing stored at index i is not a String, this will cause an error at runtime!)

Part 3: Experimenting with extension

In this section, you will explore the effects of different methods for extending an ExtensibleArray when it runs out of space.

First, download StopwatchCPU.java and add it to your Eclipse project.

Make a new class called ExtensionExperiment and add a main method, which should work as follows: First, create an empty ExtensibleArray and add the numbers 1 to 1000000 (one million) to it. Time how long this takes and print the elapsed time. To do this, create a new StopwatchCPU object at the point where you want to start timing, and then call the elapsedTime method when you are done timing. Note that StopwatchCPU counts the time actually spent running on your computer’s CPU, rather than the total time elapsed. This helps to control for the effects of other programs running on your computer simultaneously.

Now generalize the above from 1000000 to an arbitrary n:

Create an empty ExtensibleArray;
Add all the numbers from 1 to n to the ExtensibleArray;
Print the number n followed by the elapsed time.

Do this for a variety of values of n ranging up to about two million, and collect the results. At the very least you should test n = 1, 2, 4, 8, …, \(2^k\), …, \(2^{21}\).

Important: if you are getting many results of 0.0 and a few with values such as 0.015625 (which is exactly 1/64), it probably means that StopwatchCPU.java does not work properly on your computer. Try replacing StopwatchCPU.java with NanoStopwatch.java.

Make a log-log scatterplot of the data (for example, using Excel or Google Sheets). A log-log plot is one where both the X and Y axes use a logarithmic scale. Ask for help if you are not sure how to make such a plot.

Incremental vs doubling extension

Now create a new class called ExtensibleArray2 which extends ExtensibleArray, that is, which has ExtensibleArray as a superclass. To do this you can use the syntax

public class ExtensibleArray2 extends ExtensibleArray {

ExtensibleArray2 will then inherit all the methods of ExtensibleArray, except that we want to override the ensureCapacity method, to use a different method of increasing the size of the elements array. You should start by writing

@Override
protected void ensureCapacity(int capacity) {

}

Now, implement ensureCapacity so that it uses the method we discussed in class—that is, it takes the current capacity and doubles it until it is at least as big as the requested capacity. Note that the 2 at the end of ExtensibleArray2, in addition to simply denoting that it is a second type of ExtensibleArray, is also a reference to this doubling behavior.

Now edit ExtensionExperiment so that it creates an ExtensibleArray2 instead of an ExtensibleArray. That is, somewhere in ExtensionExperiment you probably have a line of code like

ExtensibleArray array = new ExtensibleArray();

You should change it to

ExtensibleArray array = new ExtensibleArray2();

Now rerun ExtensionExperiment and record the results.

Make a log-log scatterplot showing both the results from ExtensibleArray and the results from ExtensibleArray2 on the same graph.

Finally, write a paragraph discussing the results and speculating on the reasons for the observed behavior.

What to Hand In

You should turn in

ExtensibleArray.java
ExtensibleArray2.java
WordMunch.java
ExtensionExperiment.java
Your log-log scatterplots (either as an image or as a spreadsheet).
A file results.txt containing the data generated by ExtensionExperiment.java along with your paragraph discussing the results. DO NOT submit a .doc, .docx, or .pages file. These are evil, proprietary file formats designed by companies who care about making money rather than about flourishing communication between human beings.