CPSC 170 Lab 2
Searching, Sorting and 2-D Arrays

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. If there are no arguments, print a "usage" message as we discussed in class. If there is at least one argument, compute and print the average of the arguments. 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, which is unavoidable at this point.

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.
• 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.
• String toString() -- returns the list elements in a string suitable for display.

  File IntegerListTest.java contains a Java program that provides menu-driven testing for the IntegerList class. It creates a 10-element array of integers initialized to all 0s and lets you perform various operations on it. Save this file to your directory as well, then compile and run IntegerListTest to see how it works. For example, fill the list with 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. It should say "not in list." Now fill the list with new random elements. Note that the driver automatically prints the list when it is filled with new elements.

  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, but instead of including all of the sorting code inside the loop in the body of sortIncreasing, just call the following two methods (which you'll need to write):
     • private int minIndex(int start) -- takes an index start and returns the index of the smallest value in the list starting at index start.
     • private void swap(int i, int j) -- takes two indices and swaps the values in the list at those indices.

     Note that you'll have to save the value returned from the first method to pass to the second method.

     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 it 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 in increasing order for binary search to work! Don't sort it every time binary search is called -- this is too expensive -- but it's a good idea to remind the user that it should already be sorted in the menu option.

  Magic Squares

  One interesting application of two dimensional arrays is magic squares. A magic square is a square matrix in which the sum of every row, every column, and both diagonals is the same. Magic squares have been studied for many years, and there are some particularly famous magic squares. In this exercise you will write code to determine whether a square is magic.

  File Square.java contains the shell for a class that represents a square matrix. It contains headers for a constructor that gives the size of the square and methods to read values into the square, print the square, find the sum of a given row, find the sum of a given column, find the sum of the main (or other) diagonal, and determine whether the square is magic. The read method is given for you; you will need to write the others.

  File SquareTest.java contains the shell for a program that reads input for squares and tells whether each is a magic square. Following the comments, fill in the remaining code. Run your program on file magicData (you'll need to redirect the input to do this: java SquareTest < magicData) -- you should find that the first, second, and third squares in the input are magic, and that the rest (fourth through seventh) are not. Note that the -1 at the bottom tells the test program to stop reading.

  WHAT TO TURN IN:

  • Printouts of Command.java, IntegerList.java IntegerListTest.java, Square.java, and SquareTest.java.
  • Tar the files in your lab2 directory and email the .tgz file to me with cpsc170 lab2 in the Subject line.