CPSC 225, Spring 2009
Lab 2: Exceptions/Sorting

This lab has two parts, with no real connection between them. The first part of the lab asks you to find out how long it takes to sort a large array using both a sorting method that you write and using Java's built-in sorting method; this part of the lab is part of our introduction to analysis of algorithms. In the second part of the lab, you will write a program that does some simple networking and file I/O. Since these operations can generate checked exceptions, you have to use try..catch in your program to handle the potential exceptions.

You will probably want to start a new Eclipse project for this lab. However, note that a project can contain any number of programs, so you don't necessarily need a new project for every small program that you write.

Turning in your work: You will write two programs for this lab. You will generate some data using the first program -- you should include this data in a comment at the beginning of the program file. The two programs should be copied to the homework folder /classes/s09/cs225/homework/zz9999 (where, of course, you replace zz9999 with your own user name). Your work should be turned in by the beginning of next Tuesday's lab.

Part 1: Benchmarking Sorting Algorithms

The same task can take vastly different amounts of time, depending on the algorithm that is used to perform the task. You are familiar with simple sorting algorithms such as insertion sort and selection sort. (See Section 7.4 in the textbook.) While these methods work fine for small arrays, for larger arrays they can take an unreasonable amount of time. The question is whether we can do any better.

Java has some built-in sorting methods. They can be found in the class named Arrays in the package java.util. The one that you will use in this lab is Arrays.sort(A), which sorts the entire array A into increasing order. (Actually, there are different methods for different array base types, but all the methods have the same name and are used in the same way. You will be using an array of ints in this lab.)

You should write a program that does the following:

You should run your program using array sizes of 1000, 10000, and 100000. Record the sort times. Add a comment to the top of the program that reports the times. (You might be interested in applying Arrays.sort() to a million-element array, but don't try that with Selection Sort or Insertion Sort!)

Note: The general method for getting the run time of a code segment is:

           long startTime = System.currentTimeMillis();
           long runTime = System.currentTimeMillis() - startTime;

This gives the run time in milliseconds. If you want the time in seconds, you can use runTime/1000.0.


Part 2: Programming with Exceptions

In this part of the lab, you will write a program that fetches the information stored at a give URL on the web and saves that data to a file. This is partly a preview of networking and file operations and partly an exercise in using exceptions.

For doing I/O, Java has a pair of nice abstractions: InputStream and OutputStream. These are abstract classes in the package java.io. An InputStream is a place from which you can read data; an OutputStream is a place to which you can write data. For this lab, you will use an InputStream to represent the data read from the Web URL, and you will use an OutputStream to represent the file where you want to save a copy of the data. Once you have the streams, the data can be copied just by calling the following method, which you can copy into your program:

   private static void copyStream(InputStream in, OutputStream out) throws IOException {
      int oneByte = in.read();
      while (oneByte >= 0) { // negative value indicates end-of-stream
         oneByte = in.read();

Aside from this method, you should have a main routine that does the following:

Note that an exception should not crash your program. You should catch the exception and print out a reasonable error message before ending the program. It would be nice if the error message depends on the type of error that occurred (which means using several catch clauses).

I would like you to use a Scanner to get input from the user (instead of TextIO). We will talk about how to do this in class on Monday.

David Eck, for CPSC 225