You are to implement the following classes without using any Java libraries other than java.lang.Math, and that should only be needed for Math.sqrt. You may use the charAt and length methods of the String class, but not any more complicated methods of the String class. These are meant to be exercises in the use of for-loops, not exercises in the use of Java libraries. Part of the point of forbidding library functions is that many of them are implemented using for-loops, and these exercises are intended not only as programming practice but also to make you realize whether an algorithm is O(n), O(n2), O(n3), etc., by observing the depth of loop nesting. The charAt and length methods are O(1), i.e. they involve only a constant number of steps.
In each case, you will want to write a main in your class and use it yourself to test your program before submission; it doesn't matter if you leave this main in when you submit or comment it out or delete it. In any case, it won't be used when your program is tested; the submission system will use its own main to test your program.
These assignments will be graded Pass/Fail rather than by letter grade. In Fall 2007, when you pass all five assignments, that will count as an A for one programming assignment in the course. That is, the first programming assignment consists of these five review exercises.
All the assignments in this course will list some "constraints" on the inputs. These are things you can assume will be satisfied by the inputs used for testing. You do not need to do any checking for the validity of inputs in this course--your programs will be tested only with valid inputs.
Here are these review assignments, along with some comments and hints.
TwoSquares Here are some questions to ask yourself about any loop (in any problem):
(1) Am I computing something inside a loop that does not depend on the loop variable? Then compute it outside the loop instead.
(2) Is my loop bound as tight as possible? Am I looping through a lot of cases that can be ruled out and skipped?
(3) Am I computing something in the loop-test (the middle part of the for-loop) that doesn't depend on the loop variable? Then compute it beforehand.
(4) Am I computing the same thing twice within the loop? Then compute it only once and assign it to another variable.
(5) Could I write some of the initializations and updates inside the "for"? For example:
for(i=0,isq=0; isq < n; i++,isq = i*i)
instead of initializing and updating isq elsewhere. (A "comma expression" consists of two expressions separated by a comma. A comma expression is evaluated by evaluating the comma-separated expressions in left-to-right order. A for-loop needs three expressions separated by semicolons; those expressions can be comma expressions, as illustrated here.)
(6) If the loop is a while-loop, could I rewrite it as a for-loop? Usually for-loops are easier to read and maintain, and probably easier to write correctly in the first place, since they help you organize the initialization and update parts of the loop.
(7) If the loop uses break or continue or goto, are they used correctly?
(8) Did I handle the "boundary conditions" correctly? That is, the upper and lower limits of the loop, and the places where the inequality in the loop-continuation test just barely holds or just barely fails, are common sources of error, so check if you have them right or not.
TicTacToe Like the other exercises, this should use for-loops, even though they only go up to 3. Do not write eight separate pieces of code mentioning indices individually. Note, the assignment does not ask for a program that plays tic-tac-toe or determines if an incomplete game is winnable. It asks something much simpler.
Palindrome.html (Javadoc file). See also Palindrome.pdf for a complete explanation. One loop, two variables. Let one variable move right to left and the other left to right, skipping white space and punctuation, and look for a mismatch.
DuplicateSubstring. Loop over all pairs of two starting points (i,j) with i < j, and then look for a mismatch of the string starting at i with the one starting at j. When you find the mismatch, you've got the longest substring starting at both i and j. Compare that to the stored best-so-far answer. This assignment illustrates a common problem--you are breaking a loop when something happens, but what if it doesn't happen until the end of the loop? In this case, what if the characters starting from i and j match right up to the end of the string? Then that counts as a match, even though your code that stops at the first mismatched character isn't hit. Another possible error is to go beyond the array bounds looking for a mismatch.
Sudoku. Like TicTacToe, this exercise asks you to use for-loops to determine if certain rules are violated or not in a grid of characters. This time, the loops are nine-by-nine, and there is a condition on "regions" to check. Do NOT write nine separate pieces of code to check the nine regions. That too should be done by a for-loop. Number the regions from 1 to 9 and then, for each region, number the nine entries in the region from one to nine (in your mind). Calculate the corresponding rows and columns using p/3 and p%3.
Note, like TicTacToe, this problem just asks you to check if a given board is valid. It doesn't ask for a program that solves or creates Sudoku puzzles--that is much more complicated.
Here is a sample "main" that you can use to test your program on one Sudoku board at a time. It contains the sample board shown as an example in the assignment. The result should be "VALID" on this example. You can easily modify it in various ways to produce invalid examples.
public static void main(String[] args)
{
String[] x = {
"615429387",
"472853169",
"398176245",
"746231598",
"521984673",
"983765412",
"867542931",
"154397826",
"239618754"
};
System.out.println(valid(x));
}