CPSC 170 Lab 2: Timing and Two-Dimensional Arrays

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

Two-Dimensional Arrays

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.

Analyzing Runtime

Last week you modified files IntegerList.java and IntegerListTest.java to work with a class representing a list of integers. The IntegerList class contained methods to search for a value using sequential or binary search and to sort the list, among others.

Modify IntegerListTest.java (the original should be fine) so that when a menu item is selected, it prints the time required to carry out the action. Do not include the input and output (e.g., reading the value to search for). Use the java method System.currentTimeMillis() to get the time before and after the actions. Note that you will have to include java.util.* to have access to this method.

Fill in the attached table. Are these times what you expect? Explain.

Now modify IntegerList.java (again the original should be fine) so that the searches and the sort count and print the number of operations. You can approximate this with the number of loop iterations or count the other operations as well -- you choose. Again, fill in the attached table and explain your answers. Do the counts look very different from the times?

HAND IN: