CSCI 151 Lab 3: Vectors

Overview

This lab will give you chance to become more familiar with Vectors.

Materials

Setup

Create a new project in Eclipse called Lab03 (or something similar; really it does not matter what you call it).
Download Vector.java and copy it into your new Eclipse project, e.g by dragging and dropping it into the src package. (Be sure to download a new copy of Vector.java, since for the purposes of this lab I made a few tweaks to the code.)

Part 1: 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.

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 a Vector 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 a Vector, it will have the type Object. This means that something like
```
String word = myVector.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 it:
```
String word = (String)myVector.get(i);
```
(Of course, if the thing stored at index i is not a String, this will cause an error at runtime.)

Part 2: Experimenting with extension

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

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

Make a new class called VectorExperiment and add a main method.

First, create an empty Vector 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 Vector;
Add all the numbers from 1 to n to the Vector;
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²¹.

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 IncrementalVector which extends Vector, that is, which has Vector as a superclass. To do this you can use the syntax

public class IncrementalVector extends Vector {

IncrementalVector will then inherit all the methods of Vector, 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 cap) {

}

Now, implement ensureCapacity so that it uses the method you all wrote in class—that is, no matter how much capacity is requested, it allocates a new array of size cap + 100.

Now edit VectorExperiment so that it creates an IncrementalVector instead of a Vector. That is, somewhere in VectorExperiment you probably have a line of code like

Vector v = new Vector();

You should change it to

Vector v = new IncrementalVector();

Now rerun VectorExperiment and record the results.

Make a log-log scatterplot showing both the results from Vector and the results from IncrementalVector 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

WordMunch.java
VectorExperiment.java
Your log-log scatterplots (either as an image or as a spreadsheet).
A file results.txt containing the data generated by VectorExperiment.java along with your paragraph discussing the results.