CPSC 170 Lab 3
Ragged Arrays, Timings, and File I/O

As usual, create a lab3 subdirectory for today's lab, open this document in Mozilla, and start emacs.

Non-Rectangular ("Ragged") Arrays

We usually think of a two dimensional array as a table or matrix, but in Java it is also possible to create non-rectangular two dimensional arrays. There are two ways to do this:

File TwoD.java contains a shell for a program that reads in and prints out information about variable sized groups of people. This information will be stored in a two dimensional array, with each row representing one group. The program should ask the user for the number of groups and use this information to create the appropriate number of rows in the array. For each group it should then ask how many people are in the group and use this information to make that row of the array just the right length. It should then ask for the names for that group and store them in the array. After all the data has been entered, the names in each group should be listed. For example, a run of your program might look like this;

Enter number of groups: 3

Enter number of people in group 0: 2
Name 0: rachel
Name 1: elly

Enter number of people in group 1: 3
Name 0: spud
Name 1: madison
Name 2: floyd

Enter number of people in group 2: 1
Name 0: beauty

** GROUP SUMMARY **
GROUP 0: rachel elly 
GROUP 1: spud madison floyd 
GROUP 2: beauty 
In testing your program, try a group of size 0 (among others) to see what happens.

Print your program to turn in.

Timing Searching and Sorting Algorithms

File IntegerList.java contains the completed IntegerList class that you wrote in lab last week. File IntegerListTest.java contains the driver, modified to also offer some additional options (creating a list of a given size and filling the list with already sorted integers). Save these files to your directory and run IntegerListTest a few times to explore the new options.

Now you will use these classes to examine the runtimes of the sorting and searching algorithms. You can do this using the java method long System.currentTimeMillis(), which returns the current system time in milliseconds. (Note that it returns a long, not an int.) You will have to import java.util.* to have access to this method. In IntegerListTest, just get the system time immediately before and immediately after you perform any of the searches or sorts. Then subtract the first from the second, and you have the time required for the operation in milliseconds. WARNING: Be sure you are not including any input or output in your timed operations; these are very expensive and will swamp your algorithm times! Also note that the first couple of times you run a method you might get longer runtimes as it loads the code for that method. Ignore these times and use the "steady-state" times you get on subsequent runs.

Add appropriate calls to System.currentTimeMillis() to your program and fill out the tables below. Note that you will use much larger arrays for the search algorithms than for the sort algorithms; do you see why? On a separate sheet, explain the times you see in terms of the known complexities of the algorithms. Remember that the most interesting thing is not the absolute time required by the algorithms, but how the time changes as the size of the input increases.

Array size Selection sort (random array) Selection sort (sorted array) Insertion sort (random array)
10,000      
20,000      
40,000      
80,000      

Array size Sequential search (unsuccessful) Binary search (unsuccessful) Insertion sort (sorted array)
100,000      
200,000      
400,000      
800,000      
1,600,000      

File I/O

It's easy to do input and output with files in Java. To read from a text file, you construct a FileReader object, passing it the name of the file you want to read from. From your FileReader you can construct a BufferedReader, which has a nice readLine() method that lets you read one line at a time. Similarly, to write to a text file you construct a FileWriter object. From your FileWriter you can construct a PrintWriter object, which lets you use the usual print and println methods.

Note: You can find out more about the I/O classes described here in the online Java documentation. Just look up the class you want to learn about in the lower lefthand box, which lists all Java classes. Or to limit the list to just the I/O classes, select the java.io package from the list in the upper lefthand box.

File FileIO.java contains a simple program that prompts for and reads in the name of a file and then copies the contents of that file, line by line, to the standard output. Save this file to your directory, open it in emacs, and study it to see how it works. Note that to read from the file, first a FileReader is created, then it is used to create a BufferedReader. It is often convenient to use a BufferedReader because it has a readLine() method, which returns an entire line of the input (not including the newline character). Also note that the main method throws an IOException; this is just to alert the Java system that this program could generate an I/O error.

  1. Compile and run FileIO. Try it with a file that exists and with a file that does not exist.

  2. Modify FileIO so that instead of writing to the standard output, it writes to an output file. You will need to do the following:
    1. Prompt for and read in the name of the output file. In the prompt, print a message cautioning the user that if this file already exists, it will be overwritten.
    2. Use the output filename to create a FileWriter object, and use the FileWriter object to create a PrintWriter object. This is much like the way the program already creates a FileReader and a BufferedReader for input.
    3. Use the println method of the PrintWriter object you create to write each line to the output file. You are currently using the println method of the System.out object to write to the standard output, so this is a small change.
    4. After you are done writing to the output file, you must close it with its close() method. (You can call this from the PrintWriter object.) If you fail to do this, its contents will not be available.
    Test your program. Confirm that it will indeed overwrite the existing contents of a file.

  3. The warning about the output file being overwritten is not very strong. A better solution is to check and see if the file exists, and if so, inform the user that it will be overwritten and ask if they want to continue. You cannot use a FileWriter or PrintWriter object to see if a file exists; instead, you need a File object, which you can also create from the filename. Modify your program so that before it opens the output file for writing, it creates a File object for it (note that this does not create a file in the file system; this is just a Java object) and calls its boolean exists() method to see if the file already exists. If it does, warn the user as described above, and do not carry out the copy if the user says not to proceed.
Print your program to turn in.

HAND IN: