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

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.

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

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:

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:

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