CPSC 170 Lab 2
File I/O, Searching and Sorting

Command Line Arguments

1. Write a program Command.java that just prints the strings that it is given at the command line, one per line. If nothing is given at the command line, print "No arguments".

2. Modify your program so that it assumes that the arguments given at the command line are integers. Compute and print the average of the numbers given (there may be 0 or more of them). Note that you will need to use the parseInt method of the Integer class to extract integer values from the strings that are passed in. If any of the values is not numeric, your program will produce an error.

File I/O

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 begins copying, it creates a File object for the output file (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.

4. It is common to take filenames at the command line. Modify your program so that it takes two command line arguments, the input filename and the output filename, and proceeds as above. If no command line arguments are provided, the program should prompt for both files as it does now. If a different number of command line arguments are provided (instead of two), the program should print a usage message indicating that 0 or two arguments are acceptable.

Searching and Sorting

• IntegerList(int size) -- creates a new list of size elements. Elements are initialized to 0.
• void randomize() -- fills the list with random integers between 1 and 100, inclusive.
• void fillSorted() -- fills the list with integers in sorted order.
• int seqSearch(int target) -- looks for value target in the list using a sequential search algorithm. Returns the index where it first appears if it is found, -1 otherwise.
• void print() -- prints the list elements with indices.

  File IntegerListTest.java contains a Java program that provides menu-driven testing for the IntegerList class. Copy both files to your directory, and compile and run IntegerListTest to see how it works. For example, create a list of random integers, print it, and use sequential search to look for an element in the list. Does it return the correct index? Now look for an element that is not in the list. Now fill the list with sorted values and print it.

  Modify the code in these files as follows:

  1. Add a method void sortIncreasing() to the IntegerList class that uses selection sort to sort the list into increasing order. You may wish to refer to the code for selection sort on page 343 of the text.

     Add an option to the menu in IntegerListTest to test your new method.

  2. Add a method void sortDecreasing() to the IntegerList class that uses insertion sort to sort the list into decreasing order. You may wish to refer to the code for insertion sort on page 344 of the text (but note that this code sorts into increasing order, not decreasing).

     Add an option to the menu in IntegerListTest to test your new method.

  3. Add a method int binarySearch(int target) that uses binary search to look for value target in the list.It should return its index if it is found, -1 otherwise.

     Add an option to the menu in IntegerListTest to test your new method. Note that the array must be sorted for binary search to work! Don't sort it every time -- this is too expensive -- but it's a good idea to remind the user that it should already be sorted.

  4. When you are convinced that your methods work correctly, add code to time how long it takes to carry out each operation. You can do this using the java method System.currentTimeMillis(), which returns the current system time in milliseconds. (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.

     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? In the space below, explain the times you see in terms of the known complexities of the algorithms.

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

     Array size	Unsuccessful Sequential search	Unsuccessful Binary search
     100,000
     200,000
     400,000
     800,000

  HAND IN:

  • Printouts of your files plus the completed table and discussion of your results.
  • Tar the files in your lab2 directory and email the .tgz file to me with cpsc170 lab2 in the Subject line.